Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Trapping Rain Water
• Main tags: Array, Two Pointers, Dynamic Programming, Stack

What the problem is really asking

The input is an elevation map where each number is the height of a vertical bar with width 1.

After rain falls, water can sit in the valleys between taller bars. The task is to compute the total amount of water that stays trapped.

For any single position, the trapped water is determined by the shorter of:

• the tallest wall somewhere to its left
• the tallest wall somewhere to its right

That gives the core formula:

water_at_index = min(max_left, max_right) - height[index]

If that value is negative, it contributes 0.

So the whole problem is really about finding, for each bar, how high the water line can rise before it spills out on one side.

The key insight

A bar can trap water only if it has a tall enough wall on both sides.

That means the current bar itself does not decide the water level. The water level is decided by the smaller boundary around it.

This is why the problem has a strong left-right structure:

• if the left side is the limiting boundary, the amount of water on the current left bar is already known
• if the right side is the limiting boundary, the amount of water on the current right bar is already known

That observation leads to the two-pointer solution.

How to derive the optimal solution

The slow way is to stand at each index and scan outward:

• find the tallest bar to the left
• find the tallest bar to the right
• use the smaller of those two heights

That works, but it costs O(n^2).

The next improvement is to precompute those boundary heights:

• left_max[i] = tallest bar from the start through i
• right_max[i] = tallest bar from the end through i

Then each position can be evaluated in O(1), so the total time becomes O(n), with O(n) extra space.

The final improvement removes the extra arrays.

Suppose two pointers start at the ends of the array, while the algorithm keeps track of:

• the tallest wall seen so far from the left
• the tallest wall seen so far from the right

If left_max <= right_max, then the left side is the bottleneck. That means the water above the current left bar is fully determined already, because there is definitely a right boundary that is at least as tall as left_max.

So the algorithm can safely process the left bar and move left inward.

Symmetrically, if right_max < left_max, the algorithm can safely process the right bar and move right inward.

Each index is processed once, which gives:

• Time: O(n)
• Extra space: O(1)

Best approaches

• Prefix/suffix maxima: easy to derive and easy to explain. Time O(n), space O(n).
• Two pointers: same linear time, but only O(1) extra space. This is usually the best interview and production answer.
• Monotonic stack: also O(n) time and useful for reasoning about bounded valleys, but it is usually less direct than two pointers for this problem.

Why the two-pointer solution works

The only subtle part is deciding why the shorter boundary can be processed immediately.

If the best wall seen from the left is no taller than the best wall seen from the right, then the left side is the limiting side. Even if the right side changes later, it is already tall enough not to matter for the current left bar.

So the trapped water above that bar depends only on:

• left_max
• the current left bar’s height

That is why it is safe to add left_max - height[left] and move on.

The same logic applies on the right side when right_max is smaller.

This is the real invariant:

the algorithm only processes a side when that side’s best-known boundary is the smaller one, which means that side’s water level is already fixed.

Python solution

The implementation below uses the common equivalent two-pointer form that compares the current bar heights while maintaining the best boundary seen on each side.

from typing import List


class Solution:
    def trap(self, heights: List[int]) -> int:
        if len(heights) < 3:
            return 0

        return self._trap_with_two_pointers(heights)

    def _trap_with_two_pointers(self, heights: List[int]) -> int:
        left_index = 0
        right_index = len(heights) - 1
        tallest_from_left = 0
        tallest_from_right = 0
        total_trapped_water = 0

        while left_index < right_index:
            left_height = heights[left_index]
            right_height = heights[right_index]

            # The smaller side is the limiting boundary, so that side can be
            # resolved immediately.
            if left_height <= right_height:
                tallest_from_left = max(tallest_from_left, left_height)
                total_trapped_water += self._water_above_bar(
                    boundary_height=tallest_from_left,
                    bar_height=left_height,
                )
                left_index += 1
            else:
                tallest_from_right = max(tallest_from_right, right_height)
                total_trapped_water += self._water_above_bar(
                    boundary_height=tallest_from_right,
                    bar_height=right_height,
                )
                right_index -= 1

        return total_trapped_water

    @staticmethod
    def _water_above_bar(boundary_height: int, bar_height: int) -> int:
        return boundary_height - bar_height