Stage 4: Advanced Techniques·Monotonic Stack & Deque

Hard#228110 min readMonotonic StackPrefix SumLeetCode

Sum of Total Strength of Wizards

Monotonic stack with prefix-of-prefix sums

Mono stack + prefix sum of prefix sums. Tests composing techniques.

Published Apr 16, 2026

Problem

The strength of a group of wizards is defined as min(strength) * sum(strength) over the group.

Given an integer array strength, return the sum of the strengths of all contiguous non-empty subarrays, modulo 10^9 + 7.

n is up to 10^5 and each value up to 10^9, so both the brute total and any per-element O(n) scan would time out.

Input

strength = [1, 3, 1, 2]

Output

Explanation

Ten subarrays — [1]→1, [3]→9, [1]→1, [2]→4, [1,3]→4, [3,1]→4, [1,2]→3, [1,3,1]→5, [3,1,2]→6, [1,3,1,2]→7. Total 44.

Input

strength = [5, 4, 6]

Output

213

Explanation

Subarrays: [5]→25, [4]→16, [6]→36, [5,4]→4·9=36, [4,6]→4·10=40, [5,4,6]→4·15=60. Total 25+16+36+36+40+60 = 213.

Intuition

The brute approach iterates every subarray — there are O(n²) of them — and computes min * sum in O(n), giving O(n³). Completely infeasible at n = 10^5.

The first real reframe is contribution per element: rather than iterating subarrays, ask "for each index i, over how many subarrays is strength[i] the minimum, and what is the sum of their element-sums?" Add up strength[i] * (sum of those sums) across all i.

To make "strength[i] is the minimum" well-defined in the presence of duplicates, use the strictly smaller on the left / smaller-or-equal on the right convention. Let L[i] be the index of the nearest strictly smaller element to the left (or -1), and R[i] be the index of the nearest smaller-or-equal element to the right (or n). Then strength[i] is the minimum of exactly the subarrays [l..r] with L[i] < l <= i <= r < R[i].

Two monotonic-stack passes give all the L and R indices in O(n).

The second reframe is the sum-of-sums. Using prefix sums S[k] = strength[0] + ... + strength[k-1], the sum of subarray [l..r] is S[r+1] - S[l]. Summing over the valid ranges:

Σ_{l, r} (S[r+1] - S[l])
  = (i - L[i]) · Σ_{r=i}^{R[i]-1} S[r+1]
  - (R[i] - i) · Σ_{l=L[i]+1}^{i} S[l]

Both inner sums are differences of a prefix-of-prefix-sum array P[k] = S[0] + S[1] + ... + S[k-1]. Precompute P once and both sums become O(1) per i.

Everything runs modulo 1e9 + 7. Negative intermediate values (in Rust, i64) land in [-MOD, MOD), so add MOD before the final %.

Approach

Brute Force

TimeO(n³)

SpaceO(1)

Enumerate every (l, r) pair. For each, scan [l..r] to find the minimum and the sum. Multiply, accumulate.

Good for small n as a correctness baseline — this is the formula you can defend to a reviewer without any clever data structure.

impl Solution {
    pub fn total_strength(strength: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = strength.len();
        let mut total: i64 = 0;

        for l in 0..n {
            for r in l..n {
                let mut mn = strength[l];
                let mut sm: i64 = 0;
                for k in l..=r {
                    if strength[k] < mn {
                        mn= strength[k];
                    }
                    sm = strength[k] as i64;
                }
                total= (total + (mn as i64) * sm) % MOD;
            }
        }

        total as i32
    }
}

Rust · runnable

function totalStrength(strength: number[]): number {
  const MOD = 1_000_000_007n;
  const n = strength.length;
  let total = 0n;

  for (let l = 0; l < n; l++) {
    for (let r = l; r < n; r++) {
      let mn = strength[l];
      let sm = 0n;
      for (let k = l; k <= r; k++) {
        if (strength[k] < mn) mn = strength[k];
        sm += BigInt(strength[k]);
      }
      total = (total + BigInt(mn) * sm) % MOD;
    }
  }

  return Number(total);
}

TypeScript · runnable

Contribution per Element

TimeO(n²)

SpaceO(n)

Step up one level. For each index i, expand outward: walk left while elements are >= strength[i] (using strict-less-on-left, smaller-or-equal-on-right to break ties), and walk right under the symmetric rule. Now i is the min of every subarray starting in that left region and ending in that right region.

With a prefix-sum array S, the sum-of-sums over those subarrays becomes (i - L) · (S[R+1] + ... + S[i+1]) - (R - i) · (S[i] + ... + S[L+1]) (using inclusive/exclusive boundaries). Still two nested loops to find L and R per i, so O(n²) — fine for n = 10^4, too slow for 10^5.

Reads cleanly and sets up the optimal approach directly.

impl Solution {
    pub fn total_strength(strength: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = strength.len();

        // Prefix sum of strength.
        let mut pref = vec![0i64; n + 1];
        for i in 0..n {
            pref[i + 1] = pref[i] + strength[i] as i64;
        }
        // Prefix of prefix.
        let mut pp = vec![0i64; n + 2];
        for i in 0..=n {
            pp[i + 1] = (pp[i] + pref[i]) % MOD;
        }

        let mut total: i64 = 0;

        for i in 0..n {
            let v = strength[i] as i64;
            // L: nearest strictly smaller on the left (else -1).
            let mut l: i64 = (i as i64) - 1;
            while l >= 0 && strength[l as usize] as i64 >= v {
                l -= 1;
            }
            // R: nearest smaller-or-equal on the right (else n).
            let mut r: usize = i + 1;
            while r < n && (strength[r] as i64) > v {
                r += 1;
            }

            let left_count = (i as i64) - l; // i - L[i]
            let right_count = (r as i64) - (i as i64); // R[i] - i

            let sum_right = (pp[r + 1] - pp[i + 1] + MOD) % MOD;
            let sum_left = (pp[i + 1] - pp[(l + 1) as usize] + MOD) % MOD;

            let contrib = (left_count % MOD * sum_right % MOD
                - right_count % MOD * sum_left % MOD
                + MOD * MOD)
                % MOD;
            total = (total + v % MOD * contrib) % MOD;
        }

        total as i32
    }
}

Rust · runnable

function totalStrength(strength: number[]): number {
  const MOD = 1_000_000_007n;
  const n = strength.length;

  const pref = new Array<bigint>(n + 1).fill(0n);
  for (let i = 0; i < n; i++) {
    pref[i + 1]= pref[i] + BigInt(strength[i]);
  }
  const pp= new Array<bigint>(n + 2).fill(0n);
  for (let i = 0; i <= n; i++) {
    pp[i + 1]= (pp[i] + pref[i]) % MOD;
  }

  let total= 0n;

  for (let i= 0; i < n; i++) {
    const v= BigInt(strength[i]);
    let l= i - 1;
    while (l >= 0 && strength[l] >= strength[i]) l--;
    let r = i + 1;
    while (r < n && strength[r] > strength[i]) r++;

    const leftCount = BigInt(i - l);
    const rightCount = BigInt(r - i);
    const sumRight = (pp[r + 1] - pp[i + 1] + MOD) % MOD;
    const sumLeft = (pp[i + 1] - pp[l + 1] + MOD) % MOD;

    const contrib = (leftCount * sumRight - rightCount * sumLeft + MOD * MOD) % MOD;
    total = (total + v * contrib) % MOD;
  }

  return Number(total);
}

TypeScript · runnable

Monotonic Stack + Prefix-of-Prefix

TimeO(n)

SpaceO(n)

Recommended

Replace the O(n) left/right scan with two monotonic-stack passes.

Left boundaries — walk i = 0..n. Maintain a stack of indices whose strength[_] is increasing from bottom to top. While the stack's top has strength >= strength[i], pop it. After popping, the new stack top (or -1 if empty) is L[i]. Push i.
Right boundaries — walk i = (n - 1)..=0. Maintain an increasing-by-strength stack. While the top has strength > strength[i], pop. After popping, the new stack top (or n if empty) is R[i]. Push i.

The asymmetry (>= left vs > right) is how we dodge the double-count bug on duplicates: a run of equal values has exactly one index that "claims" any given subarray.

With L[i] and R[i] known, plug into the closed-form contribution:

contrib(i) = strength[i] · [ (i - L[i]) · (P[R[i]+1] - P[i+1])
                           - (R[i] - i) · (P[i+1] - P[L[i]+1]) ]

Everything mod 10^9 + 7. Total: two linear passes for L/R, one linear pass to compute prefix sums and P, one linear pass to sum contributions.

impl Solution {
    pub fn total_strength(strength: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = strength.len();
        if n == 0 {
            return 0;
        }

        // Prefix sum of strength, mod MOD at each step to stay small.
        let mut pref = vec![0i64; n + 1];
        for i in 0..n {
            pref[i + 1] = (pref[i] + strength[i] as i64) % MOD;
        }
        // Prefix of prefix: pp[k] = S[0] + S[1] + ... + S[k-1] (mod MOD).
        let mut pp = vec![0i64; n + 2];
        for i in 0..=n {
            pp[i + 1] = (pp[i] + pref[i]) % MOD;
        }

        // L[i] = nearest strictly smaller on left, -1 if none.
        let mut left = vec![-1i64; n];
        let mut stack: Vec<usize> = Vec::with_capacity(n);
        for i in 0..n {
            while let Some(&top) = stack.last() {
                if strength[top] >= strength[i] {
                    stack.pop();
                } else {
                    break;
                }
            }
            left[i] = match stack.last() {
                Some(&j) => j as i64,
                None => -1,
            };
            stack.push(i);
        }

        // R[i] = nearest smaller-or-equal on right, n if none.
        let mut right = vec![n as i64; n];
        stack.clear();
        for i in (0..n).rev() {
            while let Some(&top) = stack.last() {
                if strength[top] > strength[i] {
                    stack.pop();
                } else {
                    break;
                }
            }
            right[i] = match stack.last() {
                Some(&j) => j as i64,
                None => n as i64,
            };
            stack.push(i);
        }

        let mut total: i64 = 0;
        for i in 0..n {
            let l = left[i];
            let r = right[i];
            let left_count = ((i as i64) - l) % MOD;
            let right_count = (r - (i as i64)) % MOD;
            let sum_right = (pp[(r + 1) as usize] - pp[i + 1] + MOD) % MOD;
            let sum_left = (pp[i + 1] - pp[(l + 1) as usize] + MOD) % MOD;

            let contrib = (left_count * sum_right % MOD
                - right_count * sum_left % MOD
                + MOD * MOD)
                % MOD;
            total = (total + (strength[i] as i64) * contrib) % MOD;
        }

        total as i32
    }
}

Rust · runnable

function totalStrength(strength: number[]): number {
  const MOD = 1_000_000_007n;
  const n = strength.length;
  if (n === 0) return 0;

  const pref = new Array<bigint>(n + 1).fill(0n);
  for (let i = 0; i < n; i++) {
    pref[i + 1]= (pref[i] + BigInt(strength[i])) % MOD;
  }
  const pp= new Array<bigint>(n + 2).fill(0n);
  for (let i = 0; i <= n; i++) {
    pp[i + 1]= (pp[i] + pref[i]) % MOD;
  }

  const left= new Array<number>(n).fill(-1);
  const right = new Array<number>(n).fill(n);
  const stack: number[] = [];

  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && strength[stack[stack.length - 1]] >= strength[i]) {
      stack.pop();
    }
    left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(i);
  }

  stack.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && strength[stack[stack.length - 1]] > strength[i]) {
      stack.pop();
    }
    right[i] = stack.length === 0 ? n : stack[stack.length - 1];
    stack.push(i);
  }

  let total = 0n;
  for (let i = 0; i < n; i++) {
    const l= left[i];
    const r= right[i];
    const leftCount= BigInt(i - l);
    const rightCount= BigInt(r - i);
    const sumRight= (pp[r + 1] - pp[i + 1] + MOD) % MOD;
    const sumLeft= (pp[i + 1] - pp[l + 1] + MOD) % MOD;

    const contrib= (leftCount * sumRight - rightCount * sumLeft + MOD * MOD) % MOD;
    total= (total + BigInt(strength[i]) * contrib) % MOD;
  }

  return Number(total);
}

TypeScript · runnable

Language notes:

>= on left, > on right — the asymmetric tie-break ensures each subarray counts exactly one index as "the minimum." Equal duplicates still go in exactly one bucket.
Prefix-of-prefix-sum — the key is that Σ_{r=i}^{R-1} S[r+1] telescopes to P[R+1] - P[i+1]. Once you see it, everything folds into O(1) per element.
Mod arithmetic — i64 safely holds (n - 1) · (MOD - 1) < 2^63 for n ≤ 10^5; BigInt in TS sidesteps the question entirely but costs ~2–3× the runtime.
+ MOD * MOD — the subtraction can be negative after % MOD; add enough MODs to keep the result non-negative before the final reduction.

Trace

Contribution pass on strength = [1, 3, 1, 2]:

S = [0, 1, 4, 5, 7], P = [0, 0, 1, 5, 10, 17].

i	v	L	R	sumRight	sumLeft	contribution
0	1	-1	2	5	0	1 · (1·5 - 2·0) = 5
1	3	0	2	4	1	3 · (1·4 - 1·1) = 9
2	1	-1	4	12	5	1 · (3·12 - 2·5) = 26
3	2	2	4	7	5	2 · (1·7 - 1·5) = 4

Sum = 5 + 9 + 26 + 4 = 44.

Edge cases

All equal values — the asymmetric tie-break gives each index one non-empty window of subarrays, totaling exactly n(n+1)(n+2)/6 subarrays (each with min = sum/length ratio).
Strictly increasing — every index's left boundary is i - 1, right boundary is n. The monotonic stack peels cleanly off during the right pass.
Strictly decreasing — mirror of the above; the left pass stack has height 1, the right pass peels each element off.
Single element — L = -1, R = 1, contribution is strength[0] * strength[0].
Huge values near 10^9 — the mod keeps intermediate products bounded; without it you overflow i64 once n grows.

💡

Tip

Whenever a problem asks for a sum over all subarrays of f(min) · g(sum) or similar, the contribution-per-element pattern plus a prefix-of-prefix sum is the shape of the answer. The skeleton is: (1) nearest-smaller-on-each-side via monotonic stack, (2) closed-form sum over the valid window using two prefix arrays, (3) mod arithmetic if requested.

Takeaway

This is the graduation problem for monotonic stacks. It layers nearly every technique from earlier in this track: strict-vs-loose tie breaks (#84, #503), prefix sums, a second prefix sum over the first, and modular arithmetic hygiene.

In production, the same shape appears in risk and pricing analytics — "sum over all rolling windows of a function of the window's extremum and aggregate." Re-deriving the closed-form by hand on the whiteboard is what buys you the linear algorithm.

Hard#84

Largest Rectangle in Histogram

THE canonical mono stack problem. Must solve in under 15 minutes.

More in Monotonic Stack & Deque

Easy#496

Next Greater Element I

The basic pattern. Process right to left, stack holds candidates.

Medium#503

Next Greater Element II

Circular array — iterate twice through the array.

Hard#239

Sliding Window Maximum

Monotonic deque. Maintain decreasing order; front is always the max.

Hard#84

Largest Rectangle in Histogram

THE canonical mono stack problem. Must solve in under 15 minutes.

View #2281 on LeetCode