Widest Reservoir
MediumTwo Pointers
Problem
Engineers are planning a reservoir between two of n vertical dam walls standing in a row, one unit apart. Wall i has height heights[i].
Choosing walls i < j holds (j - i) · min(heights[i], heights[j]) units of water (walls in between are ignored). Return the largest amount any pair of walls can hold.
Example 1
- Input:
- heights = [2, 7, 3, 8, 4, 6]
- Output:
- 24
Walls 1 and 5 (heights 7 and 6) are 4 apart: 4 · 6 = 24.
Example 2
- Input:
- heights = [5, 5]
- Output:
- 5
Example 3
- Input:
- heights = [0, 9, 0]
- Output:
- 0
Constraints
- 2 ≤ heights.length ≤ 10^5
- 0 ≤ heights[i] ≤ 10^4
Hint
Show the first hint
Start with the widest possible pair: the first and last walls.
Walkthrough
How to approach it
01Clarify before coding
- Do walls between the chosen pair matter? No, only the two chosen walls and their distance.
- Can heights be zero? Yes; a zero wall holds nothing.
- Is the answer guaranteed to fit in 32 bits? The maximum is about 10^5 · 10^4 = 10^9, which fits.
02Brute force
Evaluate every pair (i, j) and keep the maximum area.
Cost: O(n²) time: 5·10^9 pairs for n = 10^5.
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.
This problem is part of Pro.