Coding interview problems › Two Pointers

↔️ Two Pointers Hard

Trapping Rain Water

Trapping Rain Water explained: water above each bar is min(left max, right max) minus its height. Two pointers solve it in O(n) time, O(1) space. Tested Python.

Also searched as: trapping rainwater problem · rain water trapping two pointers

↔️

Try it live Free

Two Pointers

Watch two pointers close in from both ends, always moving the side whose limit is already known. Trapping Rain Water uses that rule, adding up water bar by bar as the pointers move.

Also useful: Stacks & the Monotonic Stack

Open the playground →

The problem

Bars of width 1 stand side by side with non-negative heights. After it rains, water collects in the dips between taller bars. Compute the total units of water trapped.

Inputheight = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output6
Inputheight = [4, 2, 0, 3, 2, 5]
Output9

The key insight

The water above bar i is min(tallest bar to its left, tallest bar to its right) - height[i]. With two pointers you never need both maxima exactly: whichever side has the smaller running max is the side whose water level is already decided, because the other side is guaranteed to have a wall at least that tall.

Brute force first: For each bar, scanning left and right for the tallest walls is O(n²); precomputing left-max and right-max arrays is O(n) time but O(n) space.

Step-by-step approach

  1. Set i = 0, j = n - 1, and running maxima lmax = rmax = 0.
  2. While i < j: if height[i] < height[j], the left side is the limiting one.
  3. On the left: update lmax, add lmax - height[i] to the answer, move i right.
  4. Otherwise do the mirror image on the right with rmax and move j left.
  5. Return the total.

Python solution

PYTHON 3tested
def trap(height):
    i, j = 0, len(height) - 1
    lmax = rmax = water = 0
    while i < j:
        if height[i] < height[j]:      # left wall is the limit
            lmax = max(lmax, height[i])
            water += lmax - height[i]
            i += 1
        else:                          # right wall is the limit
            rmax = max(rmax, height[j])
            water += rmax - height[j]
            j -= 1
    return water

Complexity

TimeO(n)
SpaceO(1)

Each bar is processed once as one pointer moves inward. Only two running maxima and the total are stored.

Common mistakes

Frequently asked questions

What is the time and space complexity of Trapping Rain Water?

The two-pointer solution is O(n) time and O(1) space. The prefix and suffix max array solution is O(n) time and O(n) space, and the monotonic stack solution is also O(n).

Why can we decide the water at the lower side?

If height[i] < height[j], there is a wall of at least height[j] on the right, so bar i's level is set by the left maximum alone. The unknown parts of the right side cannot lower it.

How does the monotonic stack solution work?

Keep indices of decreasing heights. When a taller bar arrives, pop the bottom of a dip and add water bounded by the new bar and the bar now on top of the stack, layer by layer.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Two Pointers Two Pointers lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.