907. Sum of Subarray Minimums

Problem Description

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⁴

Python Solution

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        left = [-1] * n  # left[i] is the index of the first element smaller than arr[i] to the left
        right = [n] * n  # right[i] is the index of the first element smaller than arr[i] to the right
        stack = []
        
        # Find left boundaries
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            left[i] = stack[-1] if stack else -1
            stack.append(i)
        
        stack = []
        # Find right boundaries
        for i in range(n-1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            right[i] = stack[-1] if stack else n
            stack.append(i)
        
        # Calculate sum
        result = 0
        for i in range(n):
            # Number of subarrays where arr[i] is the minimum
            count = (i - left[i]) * (right[i] - i)
            result = (result + arr[i] * count) % MOD
        
        return result

Java Solution

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int MOD = (int)1e9 + 7;
        int n = arr.length;
        int[] left = new int[n];  // left[i] is the index of the first element smaller than arr[i] to the left
        int[] right = new int[n]; // right[i] is the index of the first element smaller than arr[i] to the right
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        
        Stack stack = new Stack<>();
        
        // Find left boundaries
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        // Find right boundaries
        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();
            stack.push(i);
        }
        
        // Calculate sum
        long result = 0;
        for (int i = 0; i < n; i++) {
            // Number of subarrays where arr[i] is the minimum
            long count = (i - left[i]) * (right[i] - i);
            result = (result + arr[i] * count) % MOD;
        }
        
        return (int)result;
    }
}

C++ Solution

class Solution {
public:
    int sumSubarrayMins(vector& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector left(n, -1);  // left[i] is the index of the first element smaller than arr[i] to the left
        vector right(n, n);  // right[i] is the index of the first element smaller than arr[i] to the right
        
        stack st;
        
        // Find left boundaries
        for (int i = 0; i < n; i++) {
            while (!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        
        while (!st.empty()) st.pop();
        
        // Find right boundaries
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }
        
        // Calculate sum
        long result = 0;
        for (int i = 0; i < n; i++) {
            // Number of subarrays where arr[i] is the minimum
            long count = (i - left[i]) * (right[i] - i);
            result = (result + arr[i] * count) % MOD;
        }
        
        return (int)result;
    }
};

JavaScript Solution

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumSubarrayMins = function(arr) {
    const MOD = 1e9 + 7;
    const n = arr.length;
    const left = new Array(n).fill(-1);  // left[i] is the index of the first element smaller than arr[i] to the left
    const right = new Array(n).fill(n);  // right[i] is the index of the first element smaller than arr[i] to the right
    
    const stack = [];
    
    // Find left boundaries
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
        stack.push(i);
    }
    
    stack.length = 0;
    // Find right boundaries
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        right[i] = stack.length === 0 ? n : stack[stack.length - 1];
        stack.push(i);
    }
    
    // Calculate sum
    let result = 0;
    for (let i = 0; i < n; i++) {
        // Number of subarrays where arr[i] is the minimum
        const count = (i - left[i]) * (right[i] - i);
        result = (result + arr[i] * count) % MOD;
    }
    
    return result;
};

C# Solution

public class Solution {
    public int SumSubarrayMins(int[] arr) {
        const int MOD = 1000000007;
        int n = arr.Length;
        int[] left = new int[n];  // left[i] is the index of the first element smaller than arr[i] to the left
        int[] right = new int[n]; // right[i] is the index of the first element smaller than arr[i] to the right
        Array.Fill(left, -1);
        Array.Fill(right, n);
        
        Stack stack = new Stack();
        
        // Find left boundaries
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) {
                stack.Pop();
            }
            left[i] = stack.Count == 0 ? -1 : stack.Peek();
            stack.Push(i);
        }
        
        stack.Clear();
        // Find right boundaries
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && arr[stack.Peek()] > arr[i]) {
                stack.Pop();
            }
            right[i] = stack.Count == 0 ? n : stack.Peek();
            stack.Push(i);
        }
        
        // Calculate sum
        long result = 0;
        for (int i = 0; i < n; i++) {
            // Number of subarrays where arr[i] is the minimum
            long count = (i - left[i]) * (right[i] - i);
            result = (result + arr[i] * count) % MOD;
        }
        
        return (int)result;
    }
}