Trapping Rain Water

hard

Calculate how much rain water can be trapped between bars

Trapping Rain Water

Key Insight

Water at i = min(maxLeft, maxRight) - height[i]. Track max from both sides.

Step 1Setup
maxL=0, maxR=0
left
0
0
1
1
0
2
2
3
1
4
0
5
1
6
3
7
2
8
1
9
2
10
right
1
11
→converge←

Track maxLeft and maxRight as pointers move inward.

1 / 5

Learn the Pattern

Two PointersUse two pointers to traverse an array or string, reducing time complexity from O(n^2) to O(n) for problems involving pairs or subarrays.
Practice the Code

Step-by-Step Walkthrough: Trapping Rain Water

Water at i = min(maxLeft, maxRight) - height[i]. Track max from both sides.

  1. Setup

    Track maxLeft and maxRight as pointers move inward.

  2. Process Left

    height[0]=0 < height[11]=1. Update maxL, no water at 0.

  3. Water Trapped

    At position 2: height=0, maxL=1. Water = 1-0 = 1.

  4. Continue

    Process all positions. Track total water.

  5. Result

    Total trapped water: 6 units