Two walls holding the most water
Medium · Target 15 minutes · Two pointers· Type asked at
Bloomberg
Optiver
Citadel
An array heights gives the heights of vertical walls standing at positions
0, 1, …, n − 1. Choose two walls; together with the ground they hold water up to the height of the
shorter one. Return the largest amount of water two walls can hold, measured as
min(heights[i], heights[j]) × (j − i).
Examples
| Input | Output | Why |
|---|---|---|
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7] | 49 | Walls 1 and 8 (heights 8 and 7): 7 × 7. |
heights = [1, 1] | 1 | The only pair. |
heights = [4, 3, 2, 1, 4] | 16 | The two outer walls, both 4, are 4 apart. |
Constraints
- 2 ≤ n ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
Hints
Hint 1
Start with the widest pair, the two ends. Every other pair is narrower, so it only wins if it is taller.
Hint 2
Compare the two end walls. Could the shorter one be part of a better pair with any wall between them?
Hint 3
No: paired with anything nearer, the width shrinks and the height is still capped by that shorter wall. Discard it and move that pointer inward.
Where people lose marks
- Moving the taller wall. The width shrinks and the height is still limited by the shorter wall, so it can only get worse; you may skip the optimum.
- Measuring the height as the taller wall, or as the sum. Water spills over the shorter one.
- Measuring the width as
hi − lo + 1. The walls have no thickness here; the distance between positions 0 and 1 is 1. - Worrying about ties. When both walls are equal, moving either is safe, since neither can be in a better pair with anything between them.
Dry run on [1,8,6,2,5,4,8,3,7]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 9heights10lo8162235445863778hiarea8best8
Walls 0 and 8: height min(1, 7) = 1, width 8, water 8 — a new best. Wall 0 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 2 / 9heights1081lo62235445863778hiarea49best49
Walls 1 and 8: height min(8, 7) = 7, width 7, water 49 — a new best. Wall 8 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 3 / 9heights1081lo622354458637hi78area18best49
Walls 1 and 7: height min(8, 3) = 3, width 6, water 18. Wall 7 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 4 / 9heights1081lo6223544586hi3778area40best49
Walls 1 and 6: height min(8, 8) = 8, width 5, water 40. Wall 6 is no taller, so no narrower pair using it can do better. Discard it.
-
Step 5 / 9heights1081lo62235445hi863778area16best49
Walls 1 and 5: height min(8, 4) = 4, width 4, water 16. Wall 5 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 6 / 9heights1081lo622354hi45863778area15best49
Walls 1 and 4: height min(8, 5) = 5, width 3, water 15. Wall 4 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 7 / 9heights1081lo6223hi5445863778area4best49
Walls 1 and 3: height min(8, 2) = 2, width 2, water 4. Wall 3 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 8 / 9heights1081lo62hi235445863778area6best49
Walls 1 and 2: height min(8, 6) = 6, width 1, water 6. Wall 2 is shorter, so no narrower pair using it can do better. Discard it.
-
Step 9 / 9heights108162235445863778best49
The pointers have met. Every pair that could have beaten 49 was examined; the answer is 49.
How to think about it
Trying every pair is O(n²). The two-pointer version starts at the widest
pair and argues, at each step, that one end can be thrown away for good.
Say heights[lo] ≤ heights[hi]. Any other pair using wall lo uses some
wall k with lo < k < hi. That container is narrower than
(lo, hi), and its height is at most heights[lo], which already caps
(lo, hi). So it holds no more water. Wall lo has had its best chance;
move lo right. The symmetric argument discards hi when it is the shorter.
Every step discards one wall, so the scan ends after n − 1 steps having examined
every pair that could be optimal.
This is the same move as "pair with a given sum", but the input is not sorted. What makes two pointers work is not sortedness; it is having a comparison that rules out one end for ever.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def most_water(heights):
lo, hi = 0, len(heights) - 1
best = 0
while lo < hi:
best = max(best, min(heights[lo], heights[hi]) * (hi - lo))
if heights[lo] < heights[hi]:
lo += 1 # the shorter wall caps every narrower pair it is in
else:
hi -= 1
return best#include <vector>
#include <algorithm>
int solve(const std::vector<int>& heights) {
int lo = 0, hi = static_cast<int>(heights.size()) - 1, best = 0;
while (lo < hi) {
best = std::max(best, std::min(heights[lo], heights[hi]) * (hi - lo));
if (heights[lo] < heights[hi]) ++lo; // the shorter wall can never do better
else --hi;
}
return best;
}class Solution {
public int mostWater(int[] heights) {
int lo = 0, hi = heights.length - 1, best = 0;
while (lo < hi) {
best = Math.max(best, Math.min(heights[lo], heights[hi]) * (hi - lo));
if (heights[lo] < heights[hi]) lo++; // the shorter wall can never do better
else hi--;
}
return best;
}
}function mostWater(heights) {
let lo = 0, hi = heights.length - 1, best = 0;
while (lo < hi) {
best = Math.max(best, Math.min(heights[lo], heights[hi]) * (hi - lo));
if (heights[lo] < heights[hi]) lo++; // the shorter wall can never do better
else hi--;
}
return best;
}fn solve(heights: &[i64]) -> i64 {
let (mut lo, mut hi) = (0usize, heights.len() - 1);
let mut best = 0i64;
while lo < hi {
best = best.max(heights[lo].min(heights[hi]) * (hi - lo) as i64);
if heights[lo] < heights[hi] {
lo += 1; // the shorter wall can never do better
} else {
hi -= 1;
}
}
best
}import Data.Array
solve :: [Int] -> Int
solve hs = go 0 (n - 1) 0
where
n = length hs
arr = listArray (0, n - 1) hs
go lo hi best
| lo >= hi = best
| l < r = go (lo + 1) hi best' -- the shorter wall can never do better
| otherwise = go lo (hi - 1) best'
where
l = arr ! lo
r = arr ! hi
best' = max best (min l r * (hi - lo))Variants to try
- Trapping rain water (the water held by all walls together, not one pair): also two pointers, carrying the highest wall seen from each side.
- Return the pair of indices, not the area.
- Skip ahead: after discarding the shorter wall, move past every wall that is no taller than it, since none of them can do better either.
Next problems
Pair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Easy12 minCount the pairs whose sum is below a target
Sort it and start at both ends, and whenever the sum's small enough you'll have found a whole run of pairs in one go.
Open the problem → Easy10 minA palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem →Write a solution and run it against the real test table.
Keep going
Pair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Easy12 minCount the pairs whose sum is below a target
Sort it and start at both ends, and whenever the sum's small enough you'll have found a whole run of pairs in one go.
Open the problem → Easy10 minA palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.