Sum of Subarray Minimums
MedPrompt
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 * 1041 <= arr[i] <= 3 * 104
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to simulate the process directly. We can generate every possible contiguous subarray, find the minimum element within each subarray, and then sum up all these minimums. This involves using nested loops to define the start and end points of the subarrays.
Algorithm
- Initialize a variable
totalSumto 0. - Use a nested loop to generate all contiguous subarrays. The outer loop with index
iwill define the start of the subarray, and the inner loop with indexjwill define the end. - For each subarray starting at
i, we can find its minimum as we extend it to the right with thejloop. - Let
currentMinbe the minimum value in the subarrayarr[i...j]. - In the inner loop, update
currentMin = min(currentMin, arr[j]). - Add this
currentMintototalSum. - Since the sum can be large, perform modulo operation at each addition to prevent overflow:
totalSum = (totalSum + currentMin) % MOD. - After iterating through all subarrays,
totalSumwill hold the final result.
Walkthrough
This method iterates through all possible starting points i of a subarray from 0 to n-1. For each starting point i, it iterates through all possible ending points j from i to n-1. This pair of (i, j) defines a subarray arr[i...j]. For each of these subarrays, we find the minimum element and add it to a running total. To find the minimum of arr[i...j] efficiently within the loops, we can maintain a variable currentMin that is updated as j increases.
class Solution { public int sumSubarrayMins(int[] arr) { int n = arr.length; long totalSum = 0; int MOD = 1_000_000_007; for (int i = 0; i < n; i++) { int currentMin = arr[i]; for (int j = i; j < n; j++) { // The minimum of subarray arr[i...j] currentMin = Math.min(currentMin, arr[j]); totalSum = (totalSum + currentMin) % MOD; } } return (int) totalSum; }}Complexity
Time
O(N^2) - There are two nested loops. The outer loop runs N times, and the inner loop runs up to N times for each outer loop iteration. This results in a quadratic time complexity.
Space
O(1) - We only use a few variables to store the running sum and current minimum, so the space complexity is constant.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides a few variables.
Cons
Highly inefficient for larger arrays.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
A more efficient approach is to change the perspective. Instead of iterating over subarrays, we can iterate over the elements of arr and calculate the contribution of each element arr[i] to the final sum. The contribution of arr[i] is arr[i] multiplied by the number of subarrays for which arr[i] is the minimum element. This number can be calculated by finding the first element to the left that is smaller than arr[i] and the first element to the right that is smaller than or equal to arr[i]. These boundaries can be found efficiently using a monotonic stack.
Algorithm
- The core idea is to calculate the contribution of each element
arr[i]to the total sum. - An element
arr[i]is the minimum in any subarrayarr[j...k]wherej <= i <= kand all other elements inarr[j...k]are greater than or equal toarr[i]. - To handle duplicates correctly and avoid overcounting, we can establish a rule:
arr[i]is the designated minimum if it's the leftmost minimum in the subarray. This means elements to its left must be strictly greater, and elements to its right can be greater than or equal. - This translates to finding the boundaries for each
arr[i]: the index of the Previous Less Element (p) and the Next Less Element (q). - The number of subarrays where
arr[i]is the minimum is(i - p) * (q - i). - We can find the
pandqfor all elements efficiently using a monotonic stack in two separate passes.- First Pass (left to right): Find the Previous Less Element (PLE) for each element. Let's call the result
leftarray whereleft[i] = i - p. - Second Pass (right to left): Find the Next Less or Equal Element (NLE) for each element. Let's call the result
rightarray whereright[i] = q - i.
- First Pass (left to right): Find the Previous Less Element (PLE) for each element. Let's call the result
- Finally, iterate through the array one more time, and for each
i, addarr[i] * left[i] * right[i]to the total sum, taking the modulo at each step.
Walkthrough
For each element arr[i], we need to find the number of subarrays where it is the minimum. A subarray is defined by a start index j and an end index k. For arr[i] to be the minimum, j must be in (p, i] and k must be in [i, q), where p is the index of the first element to the left of i that is smaller than arr[i] (Previous Less Element, PLE), and q is the index of the first element to the right of i that is smaller than or equal to arr[i] (Next Less or Equal, NLE). This tie-breaking rule (using < on the left and <= on the right) ensures each subarray is counted exactly once.
The number of choices for j is i - p, and for k is q - i. So, arr[i] is the minimum in (i - p) * (q - i) subarrays. We can compute the PLE and NLE for all elements in O(N) time using two passes with a monotonic stack.
import java.util.Deque;import java.util.ArrayDeque; class Solution { public int sumSubarrayMins(int[] arr) { int n = arr.length; int MOD = 1_000_000_007; // left[i] = number of elements to the left of i (including i) // where arr[i] is the minimum. int[] left = new int[n]; // right[i] = number of elements to the right of i (including i) // where arr[i] is the minimum. int[] right = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); // Calculate left boundaries (Previous Less Element) for (int i = 0; i < n; i++) { while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) { stack.pop(); } left[i] = i - (stack.isEmpty() ? -1 : stack.peek()); stack.push(i); } stack.clear(); // Calculate right boundaries (Next Less or Equal Element) for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) { stack.pop(); } right[i] = (stack.isEmpty() ? n : stack.peek()) - i; stack.push(i); } long totalSum = 0; for (int i = 0; i < n; i++) { long contribution = (long) arr[i] * left[i] * right[i]; totalSum = (totalSum + contribution) % MOD; } return (int) totalSum; }}Complexity
Time
O(N) - We make three separate passes through the array (one for `left`, one for `right`, and one for the final sum). Each pass takes O(N) time. Thus, the total time complexity is O(N) + O(N) + O(N) = O(N).
Space
O(N) - We use two arrays, `left` and `right`, of size N, and a stack that can grow up to size N in the worst case. Therefore, the space complexity is linear.
Trade-offs
Pros
Efficient with linear time complexity.
Guaranteed to pass within the time limits for the given constraints.
Cons
Requires O(N) extra space for the helper arrays.
Involves multiple passes over the array, which has a slightly higher constant factor than a single-pass solution.
This is the most optimized approach, building upon the monotonic stack concept. Instead of using two passes to precompute the left and right boundaries, we can calculate an element's contribution to the total sum at the exact moment it is popped from the stack. This allows us to solve the problem in a single pass.
Algorithm
- Initialize an empty monotonic stack (to store indices), and
totalSum = 0. - Iterate through the array from
i = 0ton(inclusive). Then-th iteration is for a conceptual sentinel value (0) to ensure all elements remaining in the stack are processed. - In each iteration
i, letcurrentValbearr[i](or 0 ifi == n). - While the stack is not empty and the element at the stack's top index
jis greater thancurrentVal:- This means
currentVal(at indexi) is the Next Less Element (NLE) forarr[j]. - Pop
jfrom the stack. - The element now at the top of the stack,
k, is the Previous Less or Equal Element (PLE) forarr[j]. - Calculate the contribution of
arr[j]:contribution = arr[j] * (j - k) * (i - j). - Add this contribution to
totalSum(with modulo).
- This means
- After the while loop, push the current index
ionto the stack. - After the main loop finishes,
totalSumwill hold the result.
Walkthrough
We maintain a monotonically increasing stack of indices. When we encounter a new element arr[i] that is smaller than the element at the top of the stack, arr[j], it means arr[i] is the first smaller element to the right of arr[j] (its Next Less Element). The element arr[k] that was below arr[j] on the stack is the first smaller or equal element to its left (its Previous Less or Equal Element). With these two boundaries (k and i), we can calculate the number of subarrays where arr[j] is the minimum and add its contribution to the total sum. We process all such j's from the stack before pushing i. A sentinel value (like 0) is conceptually added at the end of the array to ensure any elements remaining in the stack are popped and processed.
import java.util.Deque;import java.util.ArrayDeque; class Solution { public int sumSubarrayMins(int[] arr) { int n = arr.length; int MOD = 1_000_000_007; long totalSum = 0; // Stack stores indices of elements in increasing order of their values. Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i <= n; i++) { // Use a sentinel value (0) at the end to pop all remaining elements. int currentVal = (i == n) ? 0 : arr[i]; while (!stack.isEmpty() && arr[stack.peek()] > currentVal) { int j = stack.pop(); // j is the index of the minimum element int k = stack.isEmpty() ? -1 : stack.peek(); // k is the index of the Previous Less Element // i is the index of the Next Less Element long leftCount = j - k; long rightCount = i - j; long contribution = (long) arr[j] * leftCount * rightCount; totalSum = (totalSum + contribution) % MOD; } stack.push(i); } return (int) totalSum; }}Complexity
Time
O(N) - Each index is pushed onto and popped from the stack at most once. This results in a single pass and linear time complexity.
Space
O(N) - In the worst-case scenario (a strictly increasing array), the stack can hold all N indices.
Trade-offs
Pros
Most efficient solution with O(N) time complexity.
Requires only a single pass over the array.
Saves space by not needing explicit
leftandrightarrays.
Cons
The logic can be less intuitive to understand compared to the two-pass approach.
Solutions
Solution
class Solution {public int sumSubarrayMins(int[] arr) { int n = arr.length; int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { while (!stk.isEmpty() && arr[stk.peek()] >= arr[i]) { stk.pop(); } if (!stk.isEmpty()) { left[i] = stk.peek(); } stk.push(i); } stk.clear(); for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && arr[stk.peek()] > arr[i]) { stk.pop(); } if (!stk.isEmpty()) { right[i] = stk.peek(); } stk.push(i); } final int mod = (int)1 e9 + 7; long ans = 0; for (int i = 0; i < n; ++i) { ans += (long)(i - left[i]) * (right[i] - i) % mod * arr[i] % mod; ans %= mod; } return (int)ans; }}class Solution { public: int sumSubarrayMins ( vector < int >& arr ) { int n = arr . size (); vector < int > left ( n , - 1 ); vector < int > right ( n , n ); stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { while ( ! stk . empty () && arr [ stk . top ()] >= arr [ i ]) { stk . pop (); } if ( ! stk . empty ()) { left [ i ] = stk . top (); } stk . push ( i ); } stk = stack < int > (); for ( int i = n - 1 ; i >= 0 ; -- i ) { while ( ! stk . empty () && arr [ stk . top ()] > arr [ i ]) { stk . pop (); } if ( ! stk . empty ()) { right [ i ] = stk . top (); } stk . push ( i ); } long long ans = 0 ; const int mod = 1e9 + 7 ; for ( int i = 0 ; i < n ; ++ i ) { ans += 1LL * ( i - left [ i ]) * ( right [ i ] - i ) * arr [ i ] % mod ; ans %= mod ; } return ans ; } };class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: n = len(arr) left = [- 1] * n right = [n] * n stk = [] for i, v in enumerate(arr): while stk and arr[stk[- 1]] >= v: stk . pop() if stk: left[i] = stk[- 1] stk . append(i) stk = [] for i in range(n - 1, - 1, - 1): while stk and arr[stk[- 1]] > arr[i]: stk . pop() if stk: right[i] = stk[- 1] stk . append(i) mod = 10 ** 9 + 7 return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.