17 March 2025

LeetCode: The 'Trapping Rain Water' Problem with Two‑Pointer Approach

The 'Trapping Rain Water' problem is a good example of a question that looks visual at first and algorithmic a moment later. We're given an elevation map and asked how much water is trapped after rain. The brute‑force answer is possible, but it becomes inefficient quickly. The more interesting answer comes from recognising what information we actually need at each step.

That's where the two‑pointer approach earns its keep. It gives us a linear‑time solution without the extra arrays a prefix‑max solution would normally use.

Understanding the Core Idea

At any position, the trapped water depends on the shorter of two boundaries:

the tallest bar to the left
the tallest bar to the right

If the shorter boundary is taller than the current bar, water can sit above the bar. If not, no water is trapped there.

The usual intermediate solution precomputes left maxima and right maxima. That works well, but the two‑pointer version notices something smarter: we only need to trust the smaller side at each step.

Why the Two‑Pointer Approach Works

If the left boundary is lower than the right boundary, then the left side determines the best possible water level for the current left pointer. The right side is already tall enough not to be the limiting factor.

The same logic applies in reverse when the right boundary is lower.

That lets us move inward from both ends and solve the problem in one pass.

TypeScript Solution

export const trap = (height: number[]): number => {  let left = 0;  let right = height.length - 1;  let leftMax = 0;  let rightMax = 0;  let total = 0;  while (left < right) {    if (height[left] < height[right]) {      leftMax = Math.max(leftMax, height[left]);      total += leftMax - height[left];      left += 1;    } else {      rightMax = Math.max(rightMax, height[right]);      total += rightMax - height[right];      right -= 1;    }  }  return total;};

Walking through the Reasoning

The important detail isn't the syntax, it is the invariant:

leftMax stores the tallest wall seen so far from the left
rightMax stores the tallest wall seen so far from the right
whichever side is currently shorter can be resolved safely

That's the insight the problem is really testing. With that rule in mind, the implementation becomes quite compact.

The Alternative Worth Knowing

Before the two‑pointer version clicks, many people solve this with two auxiliary arrays: one storing the tallest wall seen from the left for every index, and one storing the tallest wall seen from the right. That is a perfectly good stepping stone.

The two‑pointer solution is really an optimisation of that idea. Instead of precomputing both arrays, we maintain just enough boundary information on the fly to resolve one side at a time.

Complexity and Edge Cases

time complexity: O(n)
space complexity: O(1)

Edge cases still matter:

arrays shorter than three bars cannot trap water
flat arrays should return 0
strictly increasing or decreasing arrays also return 0

These are precisely the cases worth covering in tests if we're writing interview‑quality or production‑quality code.

Where the Approach Seems Stranger than It is

It can sound as if we must know both exact maxima arrays before solving any index. That's true for one solution, but not for this one.

It can be just as tempting to think that two pointers are a trick. They aren't. They are a consequence of the boundary rule the problem gives us.

The original prompt and the lower‑level details behind the solution are both covered in the references below:

LeetCode problem statement

Why People Overcomplicate This One

A lot of the difficulty here comes from assuming we must know everything about every column before we can commit to an answer. That leads people towards brute‑force scans or towards precomputing arrays before they really understand what information the problem is asking for. Those are reasonable steps, but they can make the core idea look harder than it is.

The two‑pointer solution becomes much friendlier once we accept a narrower rule: at each step, the lower side is the side we can safely resolve. That is the whole trick. We do not need a perfect picture of the entire landscape before moving. We only need enough information to make the next local decision correctly.

That is also why the problem is worth revisiting after the first accepted answer. The important part is not only getting to O(n), but understanding why that local rule is safe.

That is the piece that usually makes the two‑pointer version stick in memory instead of feeling like another answer we happened to memorise once.

That shift in reasoning is usually the hardest part and the most useful part.

It turns the method back into reasoning instead of folklore.

Wrapping up

The power of the two‑pointer solution is that it turns a visual intuition into a clean invariant. When we realise the smaller boundary controls the current water level, the problem stops feeling like a memorised pattern and starts feeling like a straightforward consequence of the geometry.