LeetCode 42 Trapping Rain Water: Brute Force to O(1) Two-Pointer Deep Dive
This comprehensive guide covers LeetCode 42 Trapping Rain Water with four solutions (brute force, DP, two-pointer, monotonic stack), correctness proofs, common pitfalls, and high-frequency interview follow-ups to help candidates master optimization thinking for top-tier tech interviews.
Why Top Companies Ask This Problem
LeetCode 42 "Trapping Rain Water" appears frequently in big-tech interviews not because it is hard, but because it exposes a candidate's algorithmic intuition, optimization awareness, and communication skills within 15 minutes. Interviewers evaluate four dimensions:
Modeling ability : Abstracting "trapping water" into "min(leftMax, rightMax) - height[i]".
Optimization mindset : Progressing from O(n²) to O(1) space.
Boundary handling : Empty array, fewer than 3 bars, monotonic increasing/decreasing, flat arrays.
Communication : Explaining why moving the shorter pointer is correct.
Key advice: Don't rush to code. Restate the problem, show the thought progression, then deliver the optimal solution.
Problem Essence: The Bucket Effect
Given n non-negative integers representing bar heights (width 1), compute total trapped rainwater. Example: height = [0,1,0,2,1,0,1,3,2,1,2,1] → output 6.
Water at index i is determined by the shorter of the highest bars on both sides — the bucket effect:
water[i] = max(min(leftMax, rightMax) - height[i], 0)This formula is the core of the problem; all four solutions just compute it differently. Manual calculation on the example confirms the result 6.
Note: This intuition shares roots with LeetCode 11 "Container With Most Water" — both use two pointers and the short-board effect. Difference: LC 11 seeks a single max area; LC 42 sums all troughs.
Solution Evolution: From O(n²) to O(1) Space
Interview strategy: Show the progression, don't just dump the optimal solution.
Brute Force : Scan left/right for each column. Time O(n²), Space O(1). Interview role: explain principle only. Best for tiny data.
Dynamic Programming : Precompute leftMax / rightMax arrays. Time O(n), Space O(n). Interview role: safe transition. Best for reusing max arrays.
Two Pointers : Settle the shorter side, compute on the fly. Time O(n), Space O(1). Interview role: main answer, optimal. Best for interview & production.
Monotonic Stack : Decreasing stack, settle by "row". Time O(n), Space O(n). Interview role: bonus points. Best for streaming data, no random access.
Solution 1: Brute Force — Understand the Formula, Don't Use in Interview
// Time O(n²) | Space O(1) | Interview: explain idea only
public int trap(int[] height) {
int n = height.length, water = 0;
for (int i = 1; i < n - 1; i++) {
int leftMax = 0, rightMax = 0;
for (int j = i; j >= 0; j--) leftMax = Math.max(leftMax, height[j]);
for (int j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]);
water += Math.min(leftMax, rightMax) - height[i];
}
return water;
}Problem: Repeated scanning of left/right intervals. O(n²) times out on large inputs. Value: Helps internalize the formula and motivates optimization. Interviewers expect you to move on quickly.
Solution 2: Dynamic Programming — Classic Space-Time Tradeoff
Precompute left/right max arrays:
leftMax[i] = max(leftMax[i-1], height[i]) // left-to-right
rightMax[i] = max(rightMax[i+1], height[i]) // right-to-leftpublic int trap(int[] height) {
int n = height.length;
if (n < 3) return 0;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i-1], height[i]);
rightMax[n-1] = height[n-1];
for (int i = n-2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i+1], height[i]);
int water = 0;
for (int i = 1; i < n-1; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
return water;
}Time O(n), space O(n). Clear logic, low bug risk. Interviewer follow-up: "Can you reduce space further?"
Solution 3: Two Pointers — The Optimal Solution That Decides Pass/Fail
6.1 Key Insight: The Shorter Side's Water Level Is Determinable Immediately
Only maintain leftMax and rightMax variables, no global info. Why can we settle the current position? Because we only need to know which side is shorter.
If height[left] < height[right]:
Right side has at least height[right] (current right pointer) which is taller than height[left].
Left pointer has always been the shorter side when settling, so leftMax never exceeds the right side's maximum.
Thus min(leftMax, rightMax) = leftMax — left position's water level is locked by leftMax. Unseen bars in the middle can only raise water level, never lower it.
This is the loop invariant: the short board decides water level; the long board is just background.
6.2 Core Code (Interview-Recommended Style)
class Solution {
public int trap(int[] height) {
// Boundary guard: fewer than 3 bars cannot form a trough, also prevents NPE
if (height == null || height.length < 3) return 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
// Production: use long for water — sum may exceed Integer.MAX_VALUE
while (left < right) {
if (height[left] < height[right]) {
// Left is shorter: water level depends only on leftMax
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;
} else {
// Right is shorter (or equal): water level depends only on rightMax
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}
}Key details:
Update then settle : After updating leftMax, leftMax - height[left] >= 0, so Math.max(0, ...) is unnecessary.
Loop condition left < right : Stops when pointers meet; <= would double-count.
Equal heights go to else (move right) : Doesn't affect correctness; both styles AC.
Step-by-step trace on the example shows the "settle the shorter side" rhythm, accumulating to 6.
6.3 Technical Highlights to Mention Proactively
Highlight 1: Space compressed to the limit. Two O(n) DP arrays reduced to two variables — only 4 temporaries, O(1) extra space, cache-friendly. Highlight 2: Monotonicity guarantees no backtracking. leftMax only increases as pointer moves; each element visited once, strict O(n) time. Highlight 3: Boundaries naturally handled. Monotonic increasing array → right pointer moves left, water stays 0. Same for decreasing/flat arrays — no extra branches needed. Highlight 4: Overflow awareness. With n up to 2×10⁵ and heights up to 10⁵, total water can reach 2×10¹⁰, exceeding Integer.MAX_VALUE . Use long for accumulation, cast back at end. Mentioning this instantly separates you from rote memorizers.
If asked "Can time be lower?" answer: O(n) is the theoretical lower bound — every bar must be visited at least once. Real optimization space is in space complexity.
6.4 Two Equivalent Styles — Pick One and Master It
Style 1: Compare current heights — Condition height[l] < height[r]. Settlement: update max then settle. Most common in interviews, intuitive.
Style 2: Compare max heights — Condition leftMax < rightMax. Settlement: max(leftMax - h[l], 0) with fallback. Fewer branches, naturally handles boundaries.
Second style code:
while (left < right) {
if (leftMax < rightMax) {
totalRain += Math.max(leftMax - height[left], 0);
leftMax = Math.max(leftMax, height[left]);
left++;
} else {
totalRain += Math.max(rightMax - height[right], 0);
rightMax = Math.max(rightMax, height[right]);
right--;
}
}Third variant: check height[left] >= leftMax first — update wall if true, else settle water. All three are equivalent; choose one and stick to it.
Solution 4: Monotonic Stack — Switching from "Column" to "Row"
Previous solutions compute vertically per column. Monotonic stack computes horizontally per row, like slicing a cake: when a trough appears, settle one layer.
Rule: Maintain a decreasing stack (store indices). Scan left to right; when a bar taller than stack top appears, the right wall of a trough arrives — pop and settle.
public int trap(int[] height) {
Deque<Integer> stack = new ArrayDeque<>(); // Store indices! Heights can't compute width
int water = 0;
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = stack.pop(); // Trough bottom
if (stack.isEmpty()) break; // No left wall → can't hold water
int left = stack.peek(); // Trough left wall
int w = i - left - 1; // Width
int h = Math.min(height[left], height[i]) - height[bottom];
water += w * h; // Settle horizontally layer by layer
}
stack.push(i);
}
return water;
}Three hard-earned pitfalls:
Stack must store indices, not heights. Width = i - left - 1; storing heights makes width impossible to compute.
Break immediately if stack becomes empty after pop. No left wall means water can't be trapped; continuing causes wrong answer or NPE.
Use ArrayDeque , not Stack . Stack is legacy with synchronized overhead; ArrayDeque is faster but disallows null.
Unique value of monotonic stack: Streaming scenarios — "If data arrives as a stream with no random access, I'd use monotonic stack; it's a natural single-pass online algorithm. Two pointers need random access from both ends." This answer proves you understand trade-offs, not just memorized code.
Pitfall Guide: 8 Traps Interviewers Love to Dig
1. Think water level depends on "nearest tall bar" — Correct: Water level uses global max on each side: min(leftMax, rightMax) - h[i]. One-line answer: "Essence is finding each position's short board."
2. Don't know which pointer to move when height[l] == height[r] — Correct: Move right in else branch; correctness unaffected. One-line answer: "Both styles AC."
3. Reverse order of updating max and settling water — Correct: Update max first, then settle; keep order consistent. One-line answer: "Update first, difference always non-negative."
4. Loop condition written as left <= right — Correct: Use left < right; stop when pointers meet. One-line answer: "Less-than prevents double counting."
5. Monotonic stack stores bar heights — Correct: Store indices; width = i - left - 1. One-line answer: "Storing values loses width info."
6. Skip boundary guards — Correct: Return 0 for null or length < 3. One-line answer: "Also prevents NPE."
7. Accumulation overflow — Correct: Use long for sum, cast at end. One-line answer: "n·maxH can reach 2×10¹⁰."
8. Continue calculating after stack empty in monotonic stack — Correct: No left wall → break immediately. One-line answer: "No left wall, can't trap water."
High-Frequency Follow-Ups: Nail These 6 and You're Solid
Relation to LC 11 "Container With Most Water"? Same root: two pointers + short-board effect. LC 11 seeks single max area (distance × min height); LC 42 sums all troughs and must maintain leftMax / rightMax instead of using current heights directly.
2D/3D version? LC 407: Min-heap + BFS — expand from outermost boundary inward, water level determined by lowest confirmed boundary, aka "peeling the onion".
Array too large for memory / streaming data? Streaming monotonic stack: single pass, store only trough indices, space O(number of troughs) not O(n). For huge data, external sort + chunking.
Can it be parallelized? Divide & conquer: split at global maximum bar (natural water-level boundary), solve left/right independently — suitable for Fork/Join. DP prefix arrays can also be segmented for parallelism.
Time lower than O(n)? Impossible — each bar must be visited at least once. O(n) is theoretical lower bound; real optimization is O(n) → O(1) space.
Real-world usage? Monitoring available capacity, load-balancing resource allocation, big-data stream processing, sliding windows — "two-pointer squeeze" and "space-time tradeoff" are common patterns.
LC 407 deserves extra note: 1D logic fails in 2D because water escapes in four directions; must use min-heap from outer boundary inward, "peeling the onion" and flooding with current lowest boundary.
Interview Rhythm & Script: Five-Step Method + 60-Second Cheat Sheet
Structure your answer in five steps. Opening 30 seconds is critical — proactively lay out boundaries:
"Let me confirm: height may be null or length < 3 → return 0. Data scale ~10⁵, so O(n²) is out. Heights are non-negative; sum may overflow, so I'll use long . I'll start from brute force and progressively optimize space to O(1)."
After coding, self-test with cases:
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1})); // 6
System.out.println(s.trap(new int[]{4,2,0,3,2,5})); // 9
System.out.println(s.trap(new int[]{1,2,3})); // 0
}"Running cases: [0,1,0,2,1,0,1,3,2,1,2,1] → 6, [4,2,0,3,2,5] → 9, empty/monotonic → 0. Two pointers: O(n) time, O(1) space — optimal lower bound. Happy to discuss 2D heap solution if interested."
Closing script (memorizable):
"I started from brute force, identified the bottleneck of repeated left/right max scans; then DP preprocess to O(n) time but O(n) space; finally two pointers with bucket effect to O(1) space. One-liner: Trapping rain water = short board decides water level; two pointers let us compute local correct results without global info."
60-second emergency version:
Water per slot = min(leftMax, rightMax) - h[i] — bucket effect.
Two-pass preprocess achieves O(n) time, O(n) space.
Two pointers compress space to O(1): shorter side's water level is determinable now, settle and advance.
Accumulate with long to prevent overflow; n < 3 returns 0.
Alternative: monotonic stack (row-wise, streaming-friendly); advanced: LC 407 min-heap onion peeling.
Memory mnemonic: Column-wise check both maxes; row-wise use monotonic stack; to save space use two pointers; settle the shorter side first.
Final Takeaways
One-sentence summary: Trapping Rain Water = one bucket-effect formula + one "brute → DP → two pointers" optimization chain + one monotonic-stack row-wise bonus.
Three actionable tips:
Close this article and write the two-pointer version from memory , then explain "why moving the shorter side is correct" to someone — if you can say it, you truly know it.
Prepare the follow-up list in advance , especially LC 11 comparison and LC 407 approach, so you don't panic when asked.
Practice with engineering mindset : boundary guards, overflow protection — these small habits are the most visible gap between you and rote learners.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
