Total the bottleneck windows

HardArraysStacksMath

A row of connected taps has integer capacities. For each contiguous, nonempty window whose length is between minTaps and maxTaps inclusive, its bottleneck is the smallest capacity in that window. Return the sum of these bottlenecks over all qualifying windows. Windows at different positions count separately, even when their capacities are identical. The result is an ordinary integer: do not apply a modulus.

Example 1

INPUT[4,2,3], 1, 2OUTPUT13

Length-1 bottlenecks sum to 4 + 2 + 3 = 9. The two length-2 windows each have bottleneck 2, giving 13.

Example 2

INPUT[5,5,5], 2, 3OUTPUT15

There are two length-2 windows and one length-3 window. Each contributes 5, regardless of which equal tap is chosen as its minimum.

Keep in mind

1 <= capacities.length <= 20,000
Each capacity is an integer from 0 to 1,000,000.
1 <= minTaps <= maxTaps <= capacities.length
The answer is at most 200,010,000,000,000 and fits exactly in a JavaScript Number.

/** @returns {number} */
function solve(capacities, minTaps, maxTaps) {
  // Return the result described above.
}

/** @returns {number} */
function solve(capacities, minTaps, maxTaps) {
  // Return the result described above.
}

INPUT[4,2,3], 1, 2

EXPECTED OUTPUT13

Public samples only. These checks do not award ranked points.

AFTER THE SOLVE

How the solution works.

Walk through a solution, check its time and space costs, and compare it with yours.

Checking your progress…

Total the bottleneck windows

Example 1

Example 2

Keep in mind

How the solution works.

Related problems

Find the next cooler batch

Serve the pickup line