Trapping Rain Water with two pointers — why does leftMax/rightMax work in O(1) space?

Q: Trapping Rain Water with two pointers — why does leftMax/rightMax work in O(1) space?

**Target Audience:** Intermediate — you have seen the trapping rain water problem and can read Python; the proof is explained from scratch. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Two friends walk towards each other along a row of walls of different heights, one from each end, to measure how much rain the dips between the walls will hold. Each friend remembers only one number: the tallest wall they have passed so far. They never look ahead, never write anything down, and never go back. At first this sounds impossible. The water above a spot depe

The problem

Question presented to candidate: "You wrote the two-pointer solution to Trapping Rain Water. Convince me it is correct: the left pointer has not seen most of the right side, so why is leftMax enough to decide the water there? Walk me through it with Python code."

What a strong answer should cover:

The per-bar formula: water = min(max to the left, max to the right) - h[i], and that the left pointer knows its left max exactly.
The key bound: the right max seen so far is a lower bound on the true right wall of L, because unseen bars can only make it taller.
The invariant: if leftMax <= rightMax, then level(L) = leftMax exactly, so L can be settled; otherwise settle R symmetrically.
Why comparing heights (h[L] < h[R]) is also correct, and what goes wrong if you move the taller side.
Complexity: each step settles one bar, so O(n) time; four variables, so O(1) extra space.
Python details: Python ints cannot overflow, so the proof is the only thing to get right; tuple assignment like side, i, used = "L", lo, left_max keeps the branch short, and a randomised test against a brute force is a few lines with plain lists.

Code / implementation expected: Optional — the two-pointer loop in Python 3 plus a short argument; a brute-force cross-check is a strong bonus.

two pointers
array
Meta

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Intermediate — you have seen the trapping rain water problem and can read Python; the proof is explained from scratch.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Two friends walk towards each other along a row of walls of different heights, one from each end, to measure how much rain the dips between the walls will hold. Each friend remembers only one number: the tallest wall they have passed so far. They never look ahead, never w

The solution is hidden so you can try first

6 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTraced two-pointer run: level used vs true level for every bar

Practice

Python3,000 random arrays: two correct rules and one wrong rule vs brute force

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.