Sum of Subarray Minimums

Sum of Subarray Minimums 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.

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

• Stack Patterns pattern guide
• Monotonic Stack subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Sum of Subarray Minimums

Other problems that use the same Monotonic Stack and Stack Patterns techniques:

• 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
• Next Greater Element II — Medium, same subpattern