ASAPUtils
The signal
This is the hard one of week 1, and the reason is that the picture is intimidating while the formula is small. The unlock is refusing to think about the whole skyline:
Ask how much water sits on top of ONE bar.
For bar i, water is held in by the tallest bar to its left and the tallest bar to its right. The
lower of those two determines the level, and the bar’s own height is subtracted:
water[i] = min(maxLeft[i], maxRight[i]) - height[i] (never negative)
Total is the sum. Every solution below is just a different way of getting those two maxima.
Approach ladder
1. Brute force — O(n²)
For each i, scan left for the max and right for the max. Direct from the formula, correct, too
slow. Write this one out — it’s the version that makes the formula concrete.
2. Precompute the maxima — O(n) time, O(n) space
Two passes build maxLeft[] and maxRight[], then one pass sums. This is the honest O(n) answer
and you should be able to write it cold.
function trap(h) {
const n = h.length;
const maxLeft = new Array(n).fill(0), maxRight = new Array(n).fill(0);
let m = 0;
for (let i = 0; i < n; i++) { maxLeft[i] = m; m = Math.max(m, h[i]); }
m = 0;
for (let i = n - 1; i >= 0; i--) { maxRight[i] = m; m = Math.max(m, h[i]); }
let total = 0;
for (let i = 0; i < n; i++) total += Math.max(0, Math.min(maxLeft[i], maxRight[i]) - h[i]);
return total;
}
Notice the shape: two sweeps, one from each side. Exactly like Product of Array Except Self.
3. What is it wasting?
The two full arrays. For any given bar you don’t need both maxima exactly — you only need to know which of them is smaller, because that’s the one that sets the level.
4. The insight — O(1) space
Walk two pointers inward, carrying leftMax and rightMax as running values. At each step, look
at the shorter side:
If h[l] < h[r], then whatever rightMax turns out to be, it is at least h[r], which is
already greater than h[l]. So min(leftMax, rightMax) on the left side is definitely leftMax —
you can settle bar l right now, exactly, without ever knowing rightMax precisely.
That is the entire trick, and it’s genuinely subtle. If it doesn’t land on first reading, step through the visualizer below and watch which side gets resolved each frame.
5. Optimal
int trap(vector<int>& h) {
int l = 0, r = h.size() - 1;
int leftMax = 0, rightMax = 0, total = 0;
while (l < r) {
if (h[l] < h[r]) {
leftMax = max(leftMax, h[l]);
total += leftMax - h[l];
l++;
} else {
rightMax = max(rightMax, h[r]);
total += rightMax - h[r];
r--;
}
}
return total;
}
function trap(h) {
let l = 0, r = h.length - 1;
let leftMax = 0, rightMax = 0, total = 0;
while (l < r) {
if (h[l] < h[r]) {
leftMax = Math.max(leftMax, h[l]);
total += leftMax - h[l];
l++;
} else {
rightMax = Math.max(rightMax, h[r]);
total += rightMax - h[r];
r--;
}
}
return total;
}
Why no max(0, …) is needed in the optimal version
Because leftMax is updated to include h[l] before subtracting. So leftMax >= h[l] always,
and the contribution is never negative. In the prefix-array version maxLeft[i] excludes h[i],
so there you do need the clamp. Getting this wrong in one version and not the other is a classic
half-remembered-solution bug.
Complexity
- Time O(n), Space O(1) for the two-pointer version.
- The prefix-array version is O(n) time, O(n) space — still worth knowing, and easier to reconstruct under pressure.
Traps
- Trying to visualise the whole skyline at once. Go one bar at a time; the formula does the rest.
- Updating the running max after adding water. Order matters, per the section above.
- Comparing
leftMax < rightMaxinstead ofh[l] < h[r]. It happens to work in most cases and fails in others — derive the comparison, don’t recall it. - Assuming the answer needs a stack. A monotonic stack solution exists and is a fine week-3 revisit, but it’s more machinery than this needs.
Blank re-solve prompt
Compute the trapped rain water. Write the O(n) space version first, then the O(1) space one, and explain in one sentence why looking at the shorter side is enough.