Frontend School

Sum of Minimums of All Contiguous Subarrays

DSA
hard

Sum of Minimums of All Contiguous Subarrays

Hard
Arrays
Stack
Monotonic Stack
Dynamic Programming

Overview

In data analysis and financial modeling, understanding the behavior of minimum values within various windows or segments of a dataset is a fundamental operation. For instance, identifying the lowest stock price within all possible contiguous trading periods can reveal critical insights into market volatility. This problem challenges you to calculate the cumulative impact of these minimums across all possible contiguous subarrays.

What you need to do / Task

Given an array of integers arr, you need to find the sum of min(b) for every contiguous subarray b of arr. Since the answer may be very large, return it modulo 10^9 + 7.

Input & output

  • Input: arr: An array of integers (number[] in TypeScript, Array<number> in JavaScript).
  • Output: An integer representing the sum of minimums of all contiguous subarrays, modulo 10^9 + 7.

Clarifications

  • A contiguous subarray is a sequence of elements taken from arr that are adjacent in the original array. For example, for [1,2,3], [1,2] is a contiguous subarray, but [1,3] is not.
  • The modulo operation 10^9 + 7 should be applied at each step of the sum calculation to prevent intermediate integer overflow, ensuring the final result remains within representable limits.

Examples

1

Example 1

Input:

arr = [3,1,2,4]

Output:

17

Note:

The contiguous subarrays are: [3], min is 3 [1], min is 1 [2], min is 2 [4], min is 4 [3,1], min is 1 [1,2], min is 1 [2,4], min is 2 [3,1,2], min is 1 [1,2,4], min is 1 [3,1,2,4], min is 1 Sum = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17

2

Example 2

Input:

arr = [11,81,94,43,3]

Output:

444

Note:

Let's analyze the contribution of each element arr[i] as the minimum in subarrays: For arr[0] = 11: It's the minimum in 1 subarray to its left (itself) and 4 subarrays to its right (until 3 at index 4). Number of subarrays where 11 is the minimum = (0 - (-1)) * (4 - 0) = 1 * 4 = 4. Contribution = 11 * 4 = 44. For arr[1] = 81: Previous strictly smaller is 11 (index 0). Next smaller or equal is 43 (index 3). Number of subarrays = (1 - 0) * (3 - 1) = 1 * 2 = 2. Contribution = 81 * 2 = 162. For arr[2] = 94: Previous strictly smaller is 81 (index 1). Next smaller or equal is 43 (index 3). Number of subarrays = (2 - 1) * (3 - 2) = 1 * 1 = 1. Contribution = 94 * 1 = 94. For arr[3] = 43: Previous strictly smaller is 11 (index 0). Next smaller or equal is 3 (index 4). Number of subarrays = (3 - 0) * (4 - 3) = 3 * 1 = 3. Contribution = 43 * 3 = 129. For arr[4] = 3: Previous strictly smaller is no element (index -1). Next smaller or equal is no element (index 5). Number of subarrays = (4 - (-1)) * (5 - 4) = 5 * 1 = 5. Contribution = 3 * 5 = 15. Total sum = 44 + 162 + 94 + 129 + 15 = 444.

Constraints

Constraints & assumptions

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4
  • The final answer must be returned modulo 10^9 + 7.

Out of scope

  • Optimizations for extremely sparse arrays.
  • Handling non-integer inputs or non-positive array elements (guaranteed by constraints).

What interviewers evaluate

  • Ability to decompose the problem into subproblems (e.g., how each element contributes to the total sum).
  • Correct and efficient application of the Monotonic Stack data structure to determine the range of influence for each element.
  • Accurate handling of edge cases and array boundary conditions.
  • Proper and consistent application of modulo arithmetic throughout the computation to prevent overflow.

Loading editor...