907. Sum of Subarray Minimums
Sum of Subarray Minimums (LeetCode 907) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.
How to solve Sum of Subarray Minimums
Sum of Subarray Minimums is a Monotonic Stack problem, part of Stack Patterns. Master monotonic stack for next greater element, daily temperatures, and stock span problems.
Work towards the solution in these steps:
- Consider how a stack data structure might help efficiently track minimum values in subarrays.
- Think about using a monotonic stack to find previous and next smaller elements for each array element.
- By identifying the distance to previous and next smaller elements, you can determine how many subarrays a particular element is the minimum of.
The reference solution runs in O(n) time and O(n) space.
The Sum of Subarray Minimums solution and editorial walks through the full approach with reference code.
Problem statement
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 109 + 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 104
- 1 <= arr[i] <= 3 104
Topics and companies
Topics: Array, Dynamic Programming, Stack, Monotonic Stack.
Reported in interviews at Google, Dunzo, Microsoft, VMware.
How to practise Sum of Subarray Minimums on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Sum of Subarray Minimums in the code editor, or read the Sum of Subarray Minimums editorial for a worked solution with its approach and complexity analysis.
Where Sum of Subarray Minimums sits in the DSA pattern sheet
Problems related to Sum of Subarray Minimums
Other problems that use the same Monotonic Stack and Stack Patterns techniques:
- Car Fleet — Medium, same subpattern
- Daily Temperatures — Medium, same subpattern
- Final Prices With a Special Discount in a Shop — Easy, same subpattern
- Find the Most Competitive Subsequence — Medium, same subpattern
- Maximum Width Ramp — Medium, same subpattern
- Next Greater Element I — Easy, same subpattern
Sum of Subarray Minimums FAQ
What is the LeetCode number of Sum of Subarray Minimums?
Sum of Subarray Minimums is LeetCode problem 907, rated Medium.
What pattern is used to solve Sum of Subarray Minimums?
Sum of Subarray Minimums is a Monotonic Stack problem. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.
What is the time complexity of Sum of Subarray Minimums?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Sum of Subarray Minimums?
Sum of Subarray Minimums has been reported in interviews at Google, Dunzo, Microsoft, VMware.