LeetCode 907 - Sum of Subarray Minimums

The problem asks us to compute the sum of the minimum value of every possible contiguous subarray of a given array. For an array arr, every contiguous slice of the array is considered a subarray. For each subarray, we determine its minimum element.

leetcodemediumarraydynamic-programmingstackmonotonic-stack

LeetCode Problem 907

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Stack, Monotonic Stack

Solution

Problem Understanding

The problem asks us to compute the sum of the minimum value of every possible contiguous subarray of a given array.

For an array arr, every contiguous slice of the array is considered a subarray. For each subarray, we determine its minimum element. The final answer is the sum of all of those minimum values.

For example, if the array is:

[3,1,2]

The subarrays are:

[3]       minimum = 3
[1]       minimum = 1
[2]       minimum = 2
[3,1]     minimum = 1
[1,2]     minimum = 1
[3,1,2]   minimum = 1

The answer becomes:

3 + 1 + 2 + 1 + 1 + 1 = 9

The constraints are important:

  • The array length can be as large as 3 * 10^4
  • Each value can also be as large as 3 * 10^4

A naive solution that generates every subarray and scans for its minimum would be far too slow. Since the number of subarrays is approximately n^2, and finding the minimum naively takes another O(n) time, the total complexity could reach O(n^3).

Even an optimized brute force solution that maintains running minimums would still require O(n^2) time, which is too slow for 30,000 elements.

The problem guarantees:

  • The array is non-empty
  • All values are positive integers
  • The result may become very large, so we must return it modulo 10^9 + 7

Important edge cases include:

  • Arrays with a single element
  • Strictly increasing arrays
  • Strictly decreasing arrays
  • Arrays containing duplicate values
  • Large arrays where overflow becomes a concern

Duplicate values are especially important because they affect how we count subarrays uniquely without double counting contributions.

Approaches

Brute Force Approach

The straightforward solution is to enumerate every possible subarray.

For each starting index i, we expand the subarray to every ending index j >= i. While expanding, we maintain the minimum value seen so far.

For example:

arr = [3,1,2]

Start at index 0:
[3]       min = 3
[3,1]     min = 1
[3,1,2]   min = 1

Start at index 1:
[1]       min = 1
[1,2]     min = 1

Start at index 2:
[2]       min = 2

This avoids rescanning the entire subarray each time because we update the minimum incrementally.

The algorithm is correct because every subarray is visited exactly once, and its minimum is added to the answer.

However, the time complexity is still O(n^2), which is too slow for arrays of size 30,000.

Optimal Approach, Monotonic Stack

The key insight is that instead of asking:

"What is the minimum for every subarray?"

we can reverse the perspective and ask:

"For how many subarrays is each element the minimum?"

Suppose an element arr[i] is the minimum for some collection of subarrays. If we can count exactly how many such subarrays exist, then its total contribution becomes:

arr[i] * number_of_subarrays_where_it_is_minimum

To compute this efficiently, we determine:

  • How many consecutive elements to the left are greater than the current element
  • How many consecutive elements to the right are greater than or equal to the current element

These boundaries define all subarrays where arr[i] is the minimum.

A monotonic increasing stack allows us to find these boundaries in linear time.

The subtle handling of duplicates is crucial:

  • On one side we use strictly greater (>)
  • On the other side we use greater than or equal (>=)

This prevents duplicate minimum values from being counted multiple times.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Enumerates every subarray and tracks running minimum
Optimal O(n) O(n) Uses monotonic stack to count each element's contribution

Algorithm Walkthrough

Step 1: Compute Previous Smaller Element

For each index i, we want to know the nearest index to the left containing a strictly smaller value.

We maintain a monotonic increasing stack containing indices.

While the top of the stack has a value greater than the current value, we pop it.

After popping:

  • If the stack is empty, there is no smaller element to the left
  • Otherwise, the top of the stack is the previous smaller element

This determines how far left the current element can extend while remaining the minimum.

Step 2: Compute Next Smaller or Equal Element

Next, we compute the nearest index to the right containing a value smaller than or equal to the current value.

Again, we use a monotonic increasing stack.

This time, while the top of the stack has a value greater than or equal to the current value, we pop it.

Using >= here is critical for handling duplicates correctly.

This determines how far right the current element can extend while remaining the minimum.

Step 3: Count Valid Subarrays

For each index i:

left_count = i - previous_smaller_index
right_count = next_smaller_or_equal_index - i

The number of subarrays where arr[i] is the minimum becomes:

left_count * right_count

This works because:

  • We can independently choose any valid left boundary
  • We can independently choose any valid right boundary

The Cartesian product gives all valid subarrays.

Step 4: Add Contribution

Each element contributes:

arr[i] * left_count * right_count

We sum all contributions and take modulo 10^9 + 7.

Why it works

Every subarray has exactly one minimum element assigned to it by the boundary rules. The monotonic stack efficiently determines the maximal range where each element remains the minimum.

Using strict comparison on one side and non-strict comparison on the other guarantees that duplicate values are assigned consistently without overlap or double counting.

Python Solution

from typing import List

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)

        previous_smaller = [-1] * n
        next_smaller_equal = [n] * n

        stack = []

        # Previous smaller element
        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()

            if stack:
                previous_smaller[i] = stack[-1]

            stack.append(i)

        stack = []

        # Next smaller or equal element
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()

            if stack:
                next_smaller_equal[i] = stack[-1]

            stack.append(i)

        result = 0

        for i in range(n):
            left_count = i - previous_smaller[i]
            right_count = next_smaller_equal[i] - i

            contribution = arr[i] * left_count * right_count
            result = (result + contribution) % MOD

        return result

The implementation begins by initializing arrays that will store the nearest smaller boundaries for every element.

The first loop computes the previous smaller element for each index. The stack is maintained in increasing order of values. Whenever a larger element appears on top of the stack, it can no longer serve as a valid previous smaller boundary, so it is removed.

The second loop computes the next smaller or equal element by iterating from right to left. Using >= ensures duplicate values are handled consistently.

After both boundary arrays are built, the algorithm calculates how many subarrays each element contributes to as the minimum. The contribution formula directly follows from the number of valid left and right expansions.

Finally, the answer is accumulated modulo 10^9 + 7.

Go Solution

func sumSubarrayMins(arr []int) int {
    const MOD int = 1_000_000_007

    n := len(arr)

    previousSmaller := make([]int, n)
    nextSmallerEqual := make([]int, n)

    for i := 0; i < n; i++ {
        previousSmaller[i] = -1
        nextSmallerEqual[i] = n
    }

    stack := []int{}

    // Previous smaller element
    for i := 0; i < n; i++ {
        for len(stack) > 0 && arr[stack[len(stack)-1]] > arr[i] {
            stack = stack[:len(stack)-1]
        }

        if len(stack) > 0 {
            previousSmaller[i] = stack[len(stack)-1]
        }

        stack = append(stack, i)
    }

    stack = []int{}

    // Next smaller or equal element
    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
            stack = stack[:len(stack)-1]
        }

        if len(stack) > 0 {
            nextSmallerEqual[i] = stack[len(stack)-1]
        }

        stack = append(stack, i)
    }

    result := 0

    for i := 0; i < n; i++ {
        leftCount := i - previousSmaller[i]
        rightCount := nextSmallerEqual[i] - i

        contribution := ((arr[i] * leftCount) % MOD * rightCount) % MOD
        result = (result + contribution) % MOD
    }

    return result
}

The Go implementation follows the same algorithmic structure as the Python version.

A slice is used to simulate the stack. Elements are pushed with append and popped by reslicing.

Go requires more explicit handling of integer overflow concerns. Although the problem constraints fit within 64-bit arithmetic comfortably, modular multiplication is still applied carefully during contribution computation.

Unlike Python, Go does not automatically support negative indexing or dynamic integer sizing, so boundary initialization is handled explicitly.

Worked Examples

Example 1

arr = [3,1,2,4]

Previous Smaller Array

Index Value Stack Before Previous Smaller Stack After
0 3 [] -1 [0]
1 1 [0] -1 [1]
2 2 [1] 1 [1,2]
3 4 [1,2] 2 [1,2,3]

Result:

previous_smaller = [-1,-1,1,2]

Next Smaller or Equal Array

Index Value Stack Before Next Smaller Equal Stack After
3 4 [] 4 [3]
2 2 [3] 4 [2]
1 1 [2] 4 [1]
0 3 [1] 1 [1,0]

Result:

next_smaller_equal = [1,4,4,4]

Contribution Calculation

Index Value Left Count Right Count Contribution
0 3 1 1 3
1 1 2 3 6
2 2 1 2 4
3 4 1 1 4

Final answer:

3 + 6 + 4 + 4 = 17

Example 2

arr = [11,81,94,43,3]

Previous Smaller Array

Index Value Previous Smaller
0 11 -1
1 81 0
2 94 1
3 43 0
4 3 -1

Next Smaller or Equal Array

Index Value Next Smaller Equal
0 11 4
1 81 3
2 94 3
3 43 4
4 3 5

Contribution Calculation

Index Value Left Count Right Count Contribution
0 11 1 4 44
1 81 1 2 162
2 94 1 1 94
3 43 3 1 129
4 3 5 1 15

Final answer:

44 + 162 + 94 + 129 + 15 = 444

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is pushed and popped from the stack at most once
Space O(n) Stack and boundary arrays both require linear space

Although there are multiple passes through the array, each pass is linear. The crucial observation is that each element enters and leaves the monotonic stack at most one time, making the total stack work proportional to n.

Test Cases

from typing import List

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)

        previous_smaller = [-1] * n
        next_smaller_equal = [n] * n

        stack = []

        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()

            if stack:
                previous_smaller[i] = stack[-1]

            stack.append(i)

        stack = []

        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()

            if stack:
                next_smaller_equal[i] = stack[-1]

            stack.append(i)

        result = 0

        for i in range(n):
            left_count = i - previous_smaller[i]
            right_count = next_smaller_equal[i] - i

            result += arr[i] * left_count * right_count

        return result % (10**9 + 7)

solution = Solution()

assert solution.sumSubarrayMins([3,1,2,4]) == 17  # provided example
assert solution.sumSubarrayMins([11,81,94,43,3]) == 444  # provided example
assert solution.sumSubarrayMins([5]) == 5  # single element
assert solution.sumSubarrayMins([1,2,3,4]) == 20  # strictly increasing
assert solution.sumSubarrayMins([4,3,2,1]) == 20  # strictly decreasing
assert solution.sumSubarrayMins([2,2,2]) == 12  # duplicate values
assert solution.sumSubarrayMins([1,1,1,1]) == 10  # all equal
assert solution.sumSubarrayMins([10,9,8,7,6]) == 110  # decreasing larger values
assert solution.sumSubarrayMins([1,3,2]) == 10  # mixed ordering
assert solution.sumSubarrayMins([71,55,82,55]) == 593  # duplicate minima handling
Test Why
[3,1,2,4] Validates the basic example
[11,81,94,43,3] Tests mixed increases and decreases
[5] Smallest valid input
[1,2,3,4] Increasing sequence behavior
[4,3,2,1] Decreasing sequence behavior
[2,2,2] Duplicate handling correctness
[1,1,1,1] All equal values
[10,9,8,7,6] Larger decreasing pattern
[1,3,2] Local minimum inside array
[71,55,82,55] Tests tie-breaking logic carefully

Edge Cases

A single-element array is the simplest edge case. Since there is only one subarray, the answer must equal that element itself. Implementations that incorrectly initialize boundaries or mishandle empty stacks can fail here. This solution handles it naturally because the left and right spans both become 1.

Arrays containing duplicate values are a common source of bugs. If both boundary searches use the same comparison operator, some subarrays may be counted multiple times or missed entirely. This implementation solves that problem by using > for the previous smaller search and >= for the next smaller search, creating a consistent ownership rule for duplicates.

Strictly increasing arrays stress whether the algorithm correctly extends ranges to the left. Every element except the first has a previous smaller element immediately before it. The monotonic stack naturally preserves this structure and computes the spans correctly.

Strictly decreasing arrays create the opposite pattern. Every new element becomes the smallest so far, causing repeated stack pops. This is an important stress case for stack correctness. Even though many pops occur, each element is still pushed and popped only once overall, preserving linear time complexity.

Large arrays can produce enormous intermediate sums. Without modulo arithmetic, integer overflow could occur in some languages. The implementation applies modulo operations during accumulation to ensure correctness and compliance with the problem requirements.