algoadvance

Leetcode 907. Sum of Subarray Minimums

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 10^9 + 7.

Clarifying Questions

  1. Q: What is the expected range of the length of arr?
    • A: The length of the array can be up to 30000.
  2. Q: Can the elements in arr be negative?
    • A: No, the problem constraints guarantee that the elements in arr are positive integers.
  3. Q: What should we return when the array is empty?
    • A: Though the problem specifies the array is non-empty, it is implied we don’t need to handle such a case.

Strategy

To efficiently solve this problem, we’ll employ a stack-based approach to find out how many times each element of the array is the minimum of some subarray.

  1. Prev and Next Arrays:
    • We will use two auxiliary arrays Previous Less (prev) and Next Less (next). These arrays help to store the distance to the previous and next less element for every element in the array.
    • The prev[i] array stores the number of contiguous subarrays ending at index i where arr[i] is the minimum.
    • The next[i] array stores the number of contiguous subarrays starting at index i where arr[i] is the minimum value.
  2. Algorithm Steps:
    • Initialize prev and next arrays to store the lengths of subarrays in terms of indices.
    • Use a monotonic stack to calculate the prev array.
    • Use a monotonic stack to calculate the next array, but in a reverse iteration.
    • Calculate the result using the values from prev and next.

Code

Let’s implement the solution:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> prev(n), next(n);
        stack<int> s;

        // Calculate previous less element distances
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && arr[s.top()] >= arr[i]) {
                s.pop();
            }
            prev[i] = s.empty() ? i + 1 : i - s.top();
            s.push(i);
        }

        while (!s.empty()) s.pop(); // clear the stack

        // Calculate next less element distances
        for (int i = n - 1; i >= 0; --i) {
            while (!s.empty() && arr[s.top()] > arr[i]) {
                s.pop();
            }
            next[i] = s.empty() ? n - i : s.top() - i;
            s.push(i);
        }

        // Calculate result
        long long result = 0;
        int MOD = 1e9 + 7;
        for (int i = 0; i < n; ++i) {
            result = (result + (long long)arr[i] * prev[i] * next[i]) % MOD;
        }

        return result;
    }
};

// Example usage:
int main() {
    Solution sol;
    vector<int> arr = {3, 1, 2, 4};
    cout << sol.sumSubarrayMins(arr) << endl; // Output: 17
    return 0;
}

Time Complexity

This solution efficiently computes the sum of the minimums of all subarrays within the constraints provided.

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