Skip to main content
Talentd

Sum of Subarray Minimums - Solution & Explanation

MediumArrayDynamic ProgrammingStackMonotonic Stack29 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

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

Approach Overview

Problem Overview: Given an integer array arr, compute the sum of the minimum value of every possible subarray. A brute force enumeration would check all subarrays and track the minimum, but that becomes too slow for large inputs. The key insight is counting how many subarrays treat a specific element as the minimum.

Approach 1: Dynamic Programming with Previous Less Element (O(n) time, O(n) space)

This method combines dynamic programming with a stack that tracks the previous smaller element. For each index i, compute how many subarrays ending at i use arr[i] as the minimum. If prevLess is the nearest index to the left with a smaller value, then the contribution depends on the distance i - prevLess. A DP array stores the total contribution for subarrays ending at each index, allowing reuse of previously computed values instead of recomputing minimums. This approach reduces repeated work and builds the final answer incrementally while scanning the array once.

Approach 2: Monotonic Stack Contribution Counting (O(n) time, O(n) space)

The optimal solution uses a monotonic stack to determine the range where each element acts as the minimum. Maintain an increasing stack of indices. For every element, compute two distances: how far it can extend to the left before encountering a smaller value, and how far it can extend to the right before a strictly smaller element appears. If left represents the number of choices on the left and right on the right, the element contributes arr[i] * left * right to the total sum. Each index is pushed and popped at most once, giving linear time. This pattern appears frequently in problems involving range dominance and nearest smaller elements in an array stack workflow.

Recommended for interviews: Interviewers expect the monotonic stack solution. It demonstrates understanding of nearest-smaller-element patterns and contribution counting, both common in advanced array questions. Showing the dynamic programming interpretation first can help explain the idea, but implementing the O(n) monotonic stack approach proves you can translate the insight into an efficient solution.

Approach 1: Monotonic Stack Approach

The monotonic stack approach leverages a stack data structure to efficiently determine the minimum element of every subarray. By maintaining indexes and utilizing their properties, we can efficiently compute the sum of all minimum values for the contiguous subarrays.

This C solution employs a monotonically increasing stack to determine the number of elements affected by each element of the array on either side, thus calculating its contribution to the final sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of auxiliary arrays and a stack.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

A dynamic programming approach can also be adopted to tackle the given problem. This method involves calculating the contribution of each element to subarray minimums utilizing previously calculated results intelligently.

This C solution uses an array dp to compute subarray minimum sums progressively, allowing each integer's effect to persist cumulatively across numerous subarray possibilities.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n), arising from stack usage and dp.

Try this approach in the editor →

Approach 3: Monotonic Stack

The problem asks for the sum of the minimum values of each subarray, which is equivalent to finding the number of subarrays for which each element arr[i] is the minimum, then multiplying by arr[i], and finally summing these up.

Therefore, the focus of the problem is to find the number of subarrays for which arr[i] is the minimum. For arr[i], we find the first position left[i] to its left that is less than arr[i], and the first position right[i] to its right that is less than or equal to arr[i]. The number of subarrays for which arr[i] is the minimum is (i - left[i]) times (right[i] - i).

Note, why do we find the first position right[i] to the right that is less than or equal to arr[i], rather than less than arr[i]? This is because if we find the first position right[i] to the right that is less than arr[i], it will lead to duplicate calculations.

Let's take an example to illustrate. For the following array:

The element at index 3 is 2, the first element to its left that is less than 2 is at index 0. If we find the first element to its right that is less than 2, we get index 7. That is, the subarray interval is (0, 7). Note that this is an open interval.

0 4 3 2 5 3 2 1
*     ^       *

In the same way, we can find the subarray interval for the element at index 6, and find that its subarray interval is also (0, 7). That is, the subarray intervals for the elements at index 3 and index 6 are the same. This leads to duplicate calculations.

0 4 3 2 5 3 2 1
*           ^ *

If we find the first element to its right that is less than or equal to its value, there will be no duplication, because the subarray interval for the element at index 3 becomes (0, 6), and the subarray interval for the element at index 6 is (0, 7), which are not the same.

Back to this problem, we just need to traverse the array, for each element arr[i], use a monotonic stack to find the first position left[i] to its left that is less than arr[i], and the first position right[i] to its right that is less than or equal to arr[i]. The number of subarrays for which arr[i] is the minimum is (i - left[i]) times (right[i] - i), then multiply by arr[i], and finally sum these up.

Be aware of data overflow and modulo operations.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array arr.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Monotonic Stack Approach

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of auxiliary arrays and a stack.

Dynamic Programming Approach

Time Complexity: O(n)
Space Complexity: O(n), arising from stack usage and dp.

Monotonic Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Previous Less ElementO(n)O(n)When explaining the incremental contribution idea or building intuition with DP relations.
Monotonic Stack Contribution CountingO(n)O(n)Best general solution. Handles large inputs efficiently and is the expected interview approach.

Video Solution

L9. Sum of Subarray Minimum | Stack and Queue Playlist • take U forward • 351,168 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sum of Subarray Minimums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sum of Subarray Ranges

Next

Sum of Total Strength of Wizards