907. Sum of Subarray Minimums - Detailed Explanation

Problem Statement

Description:
Given an array of integers arr, find the sum of the minimum value of every (contiguous) subarray of arr. Since the answer can be very large, return it modulo (10^9 + 7).

Examples:

1. Example 1:

   • Input: arr = [3,1,2,4]
   • Output: 17
   • Explanation:
     The subarrays of [3,1,2,4] and their minimums are:
     • [3] → 3
     • [3,1] → 1
     • [3,1,2] → 1
     • [3,1,2,4] → 1
     • [1] → 1
     • [1,2] → 1
     • [1,2,4] → 1
     • [2] → 2
     • [2,4] → 2
     • [4] → 4
       Sum = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17

2. Example 2:

   • Input: arr = [11,81,94,43,3]
   • Output: 444
   • Explanation:
     All possible subarrays contribute to the final sum based on their minimum values.

Constraints:

• (1 \leq \text{arr.length} \leq 3 \times 10^4)
• (1 \leq \text{arr}[i] \leq 3 \times 10^4)

Hints Before the Solution

1. Brute Force Idea:
   You could generate every subarray and compute its minimum, but this approach has an O(n²) or worse time complexity and will be too slow for larger inputs.

2. Observation for Optimality:
   Instead of checking every subarray, think about the contribution of each element in arr to the final sum. If you can count how many subarrays have arr[i] as the minimum, you can multiply arr[i] by that count and add it to the sum.

3. Monotonic Stack:
   A monotonic (increasing) stack is a useful tool to determine, for each element, the span of subarrays for which it is the minimum. In particular, calculate:

   • Left Span: How many contiguous subarrays ending at i (extending to the left) where arr[i] is the smallest.
   • Right Span: How many contiguous subarrays starting at i (extending to the right) where arr[i] remains the smallest.

Approaches

Approach 1: Brute Force (For Understanding Only)

Idea:

• Iterate over all possible subarrays.
• For each subarray, compute the minimum element.
• Sum all the minimums.

Issues:

• The time complexity is O(n²) (or worse) which is impractical given the constraints.

Approach 2: Optimal Monotonic Stack Method

Idea:
For each element arr[i], determine the number of subarrays in which it is the minimum by using the following two concepts:

1. Previous Less Element:
   Find the distance from i back to the previous index where the element is strictly less than arr[i]. Let this distance be left[i] (if there is no such element, use i + 1).

2. Next Less Element:
   Find the distance from i forward to the next index where the element is less than or equal to arr[i] (to handle duplicate values correctly). Let this distance be right[i] (if there is no such element, use n - i).

Contribution of arr[i]:
Each subarray in which arr[i] is the minimum can be formed by choosing any of the left[i] choices on the left and any of the right[i] choices on the right. Therefore, the total contribution of arr[i] is:
[ \text{contribution} = \text{arr}[i] \times \text{left}[i] \times \text{right}[i] ]

Why It Works:

• By summing up the contributions from all indices, you count the minimum for every subarray exactly once.
• Using a monotonic stack, you can compute the spans in O(n) time.

Code Implementations

Python Implementation