#907

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Sum of Subarray Minimums

Calculate the sum of minimum values across all subarrays of a given array modulo 10^9 + 7.

array dynamic programming stack monotonic stack

Problem Statement

Given an array of integers arr, you need to find the sum of the minimum values of all contiguous subarrays of arr. Since the answer may be large, return the sum modulo $10^9 + 7$ .

For example, for the input arr = [3,1,2,4], the subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], and [3,1,2,4]. The corresponding minimum values are 3, 1, 2, 4, 1, 1, 2, 1, 1, and 1, and the sum of these values is 17.

Examples

Example 1

Input: arr = [3,1,2,4]

Output: 17

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

Example details omitted.

Constraints

1 <= arr.length <= 3 * 104
1 <= arr[i] <= 3 * 104

Solution Approach

Dynamic Programming with State Transitions

Use dynamic programming to keep track of the sum of minimums. Define dp[i] as the sum of minimums of all subarrays ending at index i. This approach computes the sum efficiently by leveraging state transitions from previous subarrays.

Monotonic Stack

A monotonic stack helps in determining the next smaller element for each element of the array, reducing redundant calculations. This stack-based approach optimizes the solution by ensuring every element is processed efficiently.

Modulo Operation for Large Sums

As the result can be very large, applying the modulo operation at every step ensures that the final result remains within bounds. This is crucial for avoiding overflow and meeting the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the optimal solution is O(n), where n is the length of the input array, because each element is processed at most twice (once when added to the stack and once when removed). The space complexity is O(n), primarily due to the stack and dynamic programming array.

What Interviewers Usually Probe

Ensure the candidate is comfortable explaining dynamic programming with state transitions.
Check if the candidate can optimize the solution using a monotonic stack.
Look for understanding of the modulo operation in the context of large numbers.

Common Pitfalls or Variants

Common pitfalls

Brute forcing the sum of minimums by iterating over all subarrays leads to a time complexity of O(n^2), which is inefficient for large arrays.
Misunderstanding the use of the modulo operation can result in incorrect answers, especially for large sums.
Overcomplicating the solution by using unnecessary data structures may hinder the performance of the algorithm.

Follow-up variants

Try solving this problem using a sliding window approach for further optimization.
Consider variations where the modulo is different, or the array contains negative numbers.
Attempt to solve this problem using a recursive approach with memoization.

FAQ

How do I optimize the Sum of Subarray Minimums problem?

You can optimize the problem using dynamic programming combined with a monotonic stack, reducing the time complexity to O(n).

What is the time complexity of the optimal solution?

The optimal solution has a time complexity of O(n) due to the efficient processing of each element with a monotonic stack.

What pattern does the Sum of Subarray Minimums problem follow?

This problem follows the state transition dynamic programming pattern, where each state builds upon the results of previous states.

How does a monotonic stack help in solving this problem?

A monotonic stack helps by efficiently finding the next smaller element for each element in the array, thus avoiding redundant calculations.

Why do I need to use modulo 10^9 + 7 in this problem?

Modulo 10^9 + 7 is used to prevent integer overflow and keep the result within the bounds specified by the problem constraints.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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)) % mod

Continue Practicing

#975 odd even jump #1130 minimum cost tree from leaf values #1504 count submatrices with all ones