algoadvance

Leetcode 907. Sum of Subarray Minimums

Problem Statement

Given an array of integers arr, find the sum of the minimum value of each subarray of arr. Since the answer may be large, return the sum modulo 10^9 + 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

Clarifying Questions

  1. Can the array contain negative numbers?
    • No, the problem guarantees all elements are positive integers.
  2. What is the range of the array length?
    • The array length can go up to 30000 as per the problem constraints.

Strategy

To solve this problem, we will use a stack-based approach to find the next and previous less elements for each element in the array. This method has a time complexity of O(n), where n is the length of the array.

The key idea is to determine for each element arr[i], how many subarrays that element is the minimum. We can do this efficiently by computing spans where the current element is the minimum using previous smaller element and next smaller element.

Plan

  1. Use two arrays, prev and next, where:
    • prev[i] stores the distance to the previous less element from index i.
    • next[i] stores the distance to the next less element from index i.
  2. Use two stacks to calculate prev and next:
    • One stack to determine prev array by traversing from left to right.
    • Another stack to determine next array by traversing from right to left.
  3. Calculate the sum of contributions of each element to the overall result:
    • Contribution of arr[i] to the final result is arr[i] * prev[i] * next[i] since it appears in (prev[i] + 1) * (next[i] + 1) subarrays as the minimum.
  4. Return the result modulo 10^9 + 7.

Code

import java.util.Stack;

public class Solution {
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1_000_000_007;
        int n = arr.length;
        
        // Arrays to hold the distances to the previous less and next less elements
        int[] prev = new int[n];
        int[] next = new int[n];
        
        // Initialize the stacks
        Stack<Integer> stack = new Stack<>();
        
        // Fill the prev array
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            prev[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }
        
        // Clear the stack for next use
        stack.clear();
        
        // Fill the next array
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            next[i] = stack.isEmpty() ? n - i : stack.peek() - i;
            stack.push(i);
        }
        
        // Calculate the result
        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long) arr[i] * prev[i] * next[i]) % MOD;
        }
        
        return (int) result;
    }
}

Time Complexity

The algorithm has a time complexity of O(n) due to the single pass required to fill the prev and next arrays. Each element is pushed and popped from the stack at most once.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI