Is Sum of Subarray Minimums easy or hard?

Sum of Subarray Minimums is rated Medium on LeetCode but feels challenging if you have not practiced monotonic stack problems. Once you recognize the pattern of counting element contributions using nearest smaller elements, the implementation becomes straightforward.

Sum of Subarray Minimums Python/Java solution

Python and Java implementations typically use a stack to track indices of increasing elements. While iterating through the array, elements are popped when a smaller value appears, allowing calculation of contribution ranges. The same logic works across Python, Java, C++, and JavaScript with O(n) complexity.

How to solve Sum of Subarray Minimums in O(n)?

Use a monotonic increasing stack to find the previous and next smaller elements for every index. These boundaries determine the number of subarrays where the element is the minimum. Multiply the left span, right span, and the element value to compute its contribution, then sum all contributions modulo 1e9+7.

What is the best approach for Sum of Subarray Minimums?

The best approach uses a monotonic increasing stack to determine how many subarrays treat each element as the minimum. For every index, calculate the distance to the previous smaller element and the next smaller element. Multiply these counts to determine how many subarrays include that value as the minimum. This algorithm runs in O(n) time with O(n) space.

Is Sum of Subarray Minimums asked at Google/Amazon/Meta?

Sum of Subarray Minimums appears frequently in interviews at companies that test advanced array and stack patterns, including Amazon, Google, and Meta. It evaluates knowledge of monotonic stacks, contribution counting, and efficient range analysis.

What data structure is used in Sum of Subarray Minimums?

The primary data structure is a monotonic stack that maintains indices in increasing order of values. This structure helps efficiently compute nearest smaller elements on the left and right in linear time.

What is the time complexity of Sum of Subarray Minimums?

The optimal solution runs in O(n) time because each array index is pushed to and popped from the stack at most once. Space complexity is O(n) due to the stack and auxiliary arrays used to track previous or next smaller elements.

Description Solution Video 23:35

907. Sum of Subarray Minimums

Medium39.0% acceptance13 companies

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

Constraints:

1 <= arr.length <= 3 * 10⁴
1 <= arr[i] <= 3 * 10⁴

Asked at 13 companies

Zs Associates Flipkart Sprinklr Avito

Google Amazon Morgan Stanley Microsoft Bloomberg Tiktok Apple Accenture

+1 more

Topics

23:35

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

907. Sum of Subarray Minimums

Asked at 13 companies

Topics

Similar problems