Grooming Strip Selection
Subarray indices maximizing minimum value times sum of paired weights
A ski resort divides a straight practice lane into adjacent sections. Section i has horizontal width widths[i] and usable snow depth depths[i].
A grooming machine must choose a nonempty contiguous range of sections. It removes the same depth of snow from every chosen section, and that depth cannot exceed the usable depth of any chosen section. Thus, the maximum amount of snow it can remove from sections left through right is:
min(depths[left:right + 1]) * sum(widths[left:right + 1])
Return the inclusive section indices [left, right] for a range that maximizes this amount. If several ranges have the same maximum amount, choose the one with the smallest left; if those are also equal, choose the one with the smallest right.
If there are no sections, return an empty list. Sections with zero usable depth may be selected, but any range containing one has a removable amount of zero.
Examples
Example 1
Input: depths = [4,2,5,3], widths = [1,3,1,2] Output: [0,3]
Selecting all four sections gives total width 7 and minimum depth 2, for a removable amount of 14. No narrower range provides a larger amount.
Example 2
Input: depths = [3,0,3], widths = [2,1,2] Output: [0,0]
Either outer section alone provides a removable amount of 6. Any range crossing the middle section provides zero. The tie is resolved in favor of the first section.
Example 3
Input: depths = [0,0,0], widths = [2,5,1] Output: [0,0]
Every range provides zero removable snow. The smallest possible left index is 0, and then the smallest possible right index is also 0.
Constraints
- 0 <= depths.length <= 10000
- widths.length == depths.length
- 0 <= depths[i] <= 100000
- 1 <= widths[i] <= 100000
The intended solution takes O(n) time and O(n) auxiliary space. Removable amounts can exceed 32-bit integer range, but remain exactly representable by JavaScript numbers under the stated constraints.
Hints
Show hint 1Hint 1
For a positive minimum depth, extending a range across another section with at least that depth strictly increases the removable amount.
Show hint 2Hint 2
Keep section indices in a stack with nondecreasing depths. When a shallower section arrives, popped indices identify ranges whose right boundary is now known; prefix sums give their total widths.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the maximum removable amount and the uniform removal depth?
- If every section had width 1, which part of the implementation could you eliminate?
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