Total of Window Minimums

MediumStack

Problem

For an array of positive integers arr, consider every contiguous subarray and take its minimum. Return the sum of all those minimums.

Because the sum can be huge, return it modulo 1 000 000 007.

Example 1

Input:
arr = [2, 4, 1]
Output:
11

Minimums: [2]=2, [4]=4, [1]=1, [2,4]=2, [4,1]=1, [2,4,1]=1. Sum 11.

Example 2

Input:
arr = [5, 5]
Output:
15

Both singletons and the pair have minimum 5.

Constraints

  • 1 ≤ arr.length ≤ 3·10^4
  • 1 ≤ arr[i] ≤ 3·10^4

Hint

Show the first hint

Instead of looping over subarrays, ask: for how many subarrays is arr[i] the minimum?

Walkthrough

How to approach it

01Clarify before coding

  • Why the modulus? With n = 3·10^4 the true sum can exceed 10^13.
  • How should equal values be handled? Each subarray must be counted exactly once; pick a tie rule.

02Brute force

For each start l, extend r and maintain the running minimum, adding it to the total.

Cost: O(n²): 4.5·10^8 steps for n = 3·10^4, too slow.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.