How do you solve Sum of Subarray Minimums on LeetCode?

Sum of Subarray Minimums (LeetCode #907) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a monotonic stack can significantly reduce the time complexity.

What is the brute force solution for Sum of Subarray Minimums?

The brute force approach for Sum of Subarray Minimums is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible subarrays and calculating the minimum for each one. While this is straightforward, it is inefficient for larger arrays due to the number of subarrays growing quadratically. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Sum of Subarray Minimums?

Sum of Subarray Minimums uses the following concepts: Array, Dynamic Programming, Stack, Monotonic Stack. The recommended patterns to study are: Monotonic Stack, Dynamic Programming.

What are the interview tips for Sum of Subarray Minimums?

Explain your thought process clearly while coding. Be prepared to discuss time and space complexity. Practice writing clean and efficient code.

What are common mistakes when solving Sum of Subarray Minimums?

Not using a stack correctly to find previous/next smaller elements. Forgetting to take modulo at each step to avoid overflow.

#907

Sum of Subarray Minimums

Medium

ArrayDynamic ProgrammingStackMonotonic StackMonotonic StackDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a monotonic stack to efficiently calculate how many subarrays each element is the minimum for. This reduces the need to explicitly generate all subarrays.

⚙️

Algorithm

4 steps

1Step 1: Initialize a stack and an array to store the contribution of each element.
2Step 2: For each element, determine how many subarrays it is the minimum for using the stack to find the previous and next smaller elements.
3Step 3: Calculate the contribution of each element to the total sum based on its position and the number of subarrays it is the minimum for.
4Step 4: Return the total sum modulo 10^9 + 7.

solution.py32 lines

1# Full working Python code
2
3def sumSubarrayMinimums(arr):
4    MOD = 10**9 + 7
5    n = len(arr)
6    stack = []
7    total_sum = 0
8    left = [0] * n
9    right = [0] * n
10
11    for i in range(n):
12        while stack and arr[stack[-1]] > arr[i]:
13            stack.pop()
14        left[i] = i + 1 if not stack else i - stack[-1]
15        stack.append(i)
16
17    stack.clear()
18
19    for i in range(n - 1, -1, -1):
20        while stack and arr[stack[-1]] >= arr[i]:
21            stack.pop()
22        right[i] = n - i if not stack else stack[-1] - i
23        stack.append(i)
24
25    for i in range(n):
26        total_sum += arr[i] * left[i] * right[i]
27        total_sum %= MOD
28
29    return total_sum
30
31# Example usage
32print(sumSubarrayMinimums([3, 1, 2, 4]))

ℹ

Complexity note: The time complexity is O(n) because we traverse the array a constant number of times (once for left and once for right). The space complexity is O(n) due to the additional arrays used to store left and right counts.

1Using a monotonic stack can significantly reduce the time complexity.
2Understanding how to calculate contributions of each element is key.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.