Faangprep Logo
LoginRegister
Two Pointers
Hard

Trapping Rain Water

Compute how much water can be trapped after raining.
10 min read
Solve on LeetCode
Examples
Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output:6
Explain:

The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of rain water.

Problem Understanding

The Goal

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Imagine looking at the side profile of a structure built with blocks. When it rains, water fills the "valleys" formed between taller "peaks".

Key Insight

For any given bar at index i, the amount of water it can hold above it is determined by:
min(max_height_to_left, max_height_to_right) - height[i]

If this value is negative, it means the bar is taller than the water level, so it holds 0 water.

Algorithm Strategy

The Two Pointer Approach

Instead of pre-computing the max height to the left and right for every index (which takes O(n) space), we can use two pointers to solve this in O(n) time and O(1) space.

  1. Initialize left = 0 and right = n - 1.
  2. Track leftMax and rightMax seen so far.
  3. The Logic: The amount of water trapped at a position is limited by the shorter of the two boundaries.
    • If leftMax < rightMax: We know the water level at the left pointer is determined by leftMax (because there's a taller wall somewhere on the right). We calculate water for left, update leftMax, and move left forward.
    • If leftMax >= rightMax: We know the water level at the right pointer is determined by rightMax (because there's a taller wall somewhere on the left). We calculate water for right, update rightMax, and move right backward.
Interactive Visualization
Step 1 / 14
0
L
1
0
2
1
0
1
3
2
1
2
1
R

Start with pointers at ends.Left Max: 0, Right Max: 1.

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep