DSA Tracker

Visualize

Sum of Subarray Minimums

Monotonic increasing stack, counting who owns each subarray

time O(n)space O(n)

Listing every subarray is quadratic before you even look at it, so flip the question around: instead of asking each subarray for its minimum, ask each element how many subarrays it is the minimum of. An element owns exactly the stretch between the nearest smaller element on its left and the nearest smaller on its right — pick any left end inside that stretch and any right end, and it is the smallest thing in between. That makes its count a simple product of two distances. A monotonic increasing stack of indices finds both boundaries in one pass: the moment a smaller value arrives, every stacked element bigger than it has just met its right boundary, and whatever sits below it on the stack is its left boundary. Duplicates are the one trap — pop on >= so equal values break leftwards, or a subarray whose minimum appears twice gets counted twice.

Details

Animated on: arr = [3, 1, 2, 4, 3, 1] — add up the minimum of every one of its 21 contiguous subarrays. Answer: 33.

Problem:Sum of Subarray MinimumsMedium

Monotonic increasing stack, counting who owns each subarray

step 1 / 14

3
[0]
1
[1]
2
[2]
4
[3]
3
[4]
1
[5]
0
[6]

arr = 3, 1, 2, 4, 3, 1, with a 0 pinned on at index 6 that is smaller than everything so every real element gets forced off the stack and paid for. Instead of listing all 21 subarrays, ask of each element: how many subarrays is IT the minimum of? Multiply that count by its value and add up.

  • i=0· arr[0] = 3
Pseudocode
1FUNCTION sumSubarrayMins(A):
2  APPEND 0 TO A
3  stack <- [-1]
4  total <- 0
5  FOR i <- 0 TO LENGTH(A) - 1:
6    WHILE TOP(stack) != -1 AND A[TOP(stack)] >= A[i]:
7      j <- POP(stack)
8      total <- total + A[j] * (j - TOP(stack)) * (i - j)
9    PUSH i ONTO stack
10  RETURN total

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. arr = 3, 1, 2, 4, 3, 1, with a 0 pinned on at index 6 that is smaller than everything so every real element gets forced off the stack and paid for. Instead of listing all 21 subarrays, ask of each element: how many subarrays is IT the minimum of? Multiply that count by its value and add up.
  2. Nothing is left on the stack, so arr[0] = 3 is the smallest value seen so far and its window is still open at both ends — push it and read on. Stack holds [0].
  3. arr[1] = 1 is smaller than arr[0] = 3, so index 0 can never be the minimum of anything reaching index 1 or beyond — its window is closed, settle it now. It owns indices 0..0: 1 way to pick a left end x 1 way to pick a right end = 1 subarray, adding 3 x 1 = 3. Running total 3.
  4. Nothing is left on the stack, so arr[1] = 1 is the smallest value seen so far and its window is still open at both ends — push it and read on. Stack holds [1].
  5. Everything still stacked is strictly smaller than arr[2] = 2, so index 2 is the smallest thing seen since index 1 and its window can still grow rightwards — push it and read on. Stack holds [1, 2], values 1 < 2 climbing left to right.
  6. Everything still stacked is strictly smaller than arr[3] = 4, so index 3 is the smallest thing seen since index 2 and its window can still grow rightwards — push it and read on. Stack holds [1, 2, 3], values 1 < 2 < 4 climbing left to right.
  7. arr[4] = 3 is smaller than arr[3] = 4, so index 3 can never be the minimum of anything reaching index 4 or beyond — its window is closed, settle it now. It owns indices 3..3: 1 way to pick a left end x 1 way to pick a right end = 1 subarray, adding 4 x 1 = 4. Running total 7.
  8. Everything still stacked is strictly smaller than arr[4] = 3, so index 4 is the smallest thing seen since index 2 and its window can still grow rightwards — push it and read on. Stack holds [1, 2, 4], values 1 < 2 < 3 climbing left to right.
  9. arr[5] = 1 is smaller than arr[4] = 3, so index 4 can never be the minimum of anything reaching index 5 or beyond — its window is closed, settle it now. It owns indices 3..4: 2 ways to pick a left end x 1 way to pick a right end = 2 subarrays, adding 3 x 2 = 6. Running total 13.
  10. arr[5] = 1 is smaller than arr[2] = 2, so index 2 can never be the minimum of anything reaching index 5 or beyond — its window is closed, settle it now. It owns indices 2..4: 1 way to pick a left end x 3 ways to pick a right end = 3 subarrays, adding 2 x 3 = 6. Running total 19.
  11. arr[5] = 1 EQUALS arr[1], and the tie is broken in favour of the newcomer: index 1 stops here so the same subarray is never counted twice. Its reach is indices 0..4, giving 2 left choices x 4 right choices = 8 subarrays it is the minimum of, adding 1 x 8 = 8. Running total 27.
  12. Nothing is left on the stack, so arr[5] = 1 is the smallest value seen so far and its window is still open at both ends — push it and read on. Stack holds [5].
  13. arr[6] = 0 is smaller than arr[5] = 1, so index 5 can never be the minimum of anything reaching index 6 or beyond — its window is closed, settle it now. It owns indices 0..5: 6 ways to pick a left end x 1 way to pick a right end = 6 subarrays, adding 1 x 6 = 6. Running total 33.
  14. The 0 sentinel emptied the stack, so every real index was pushed once and popped once and each of the 21 subarrays was charged to exactly one owner — the one element that is its minimum. Sum of all subarray minimums: 33.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Sum of Subarray Minimums in the editorAll Stack problemsBack to roadmap