Marathon Recovery Ledger
Sum of each subarray's minimum times its sum, modulo 1,000,000,007
A marathon organizer records a positive strain score for each kilometer of a training route. The scores, in route order, are stored in strain.
For every nonempty contiguous block of kilometers, the organizer defines its recovery burden as:
the smallest strain score in the block × the sum of all strain scores in the block.
The recovery ledger must include every nonempty contiguous block exactly once, including single-kilometer blocks.
Return the sum of their recovery burdens, modulo 1,000,000,007.
Examples
Example 1
Input: strain = [3,1,2] Output: 27
The route has six nonempty contiguous blocks. For the entire route, the smallest score is 1 and the sum of the scores is 6. Apply the same burden rule to the three single-kilometer blocks and the two length-two blocks, then add all six burdens.
Example 2
Input: strain = [5,5] Output: 100
Both single-kilometer blocks and the complete two-kilometer block belong in the ledger. Equal minimum scores do not cause a block to be counted more than once.
Example 3
Input: strain = [7] Output: 49
There is only one block. Its minimum and its sum are both the single kilometer's strain score.
Constraints
- 1 <= strain.length <= 12,000
- 1 <= strain[i] <= 1,000,000,000
- Return the answer modulo 1,000,000,007.
The intended complexity is O(n) time and O(n) auxiliary space. Intermediate products can exceed JavaScript's exact integer range; use BigInt or another exact modular arithmetic technique.
Hints
Show hint 1Hint 1
Assign each block to its rightmost occurrence of the minimum score. A monotonic stack can find how far a block assigned to each index may extend in either direction.
Show hint 2Hint 2
For a fixed assigned index, express each block's sum as the difference of two prefix sums. A second layer of prefix sums lets you aggregate all choices of endpoints without enumerating them.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return one contribution per index, assigning each block to its rightmost minimum?
- How would the solution change if the minimum came from one array, but the block's sum came from a separate array of nonnegative kilometer weights?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem