Trapping Rain Water

Calculate how much water can be trapped between bars.

Pattern

Two Pointers / Prefix Max

This problem follows the Two Pointers / Prefix Max pattern, commonly found in the Two Pointers category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

Track maxLeft and maxRight. Water at each position = min(maxL, maxR) - height.

Key Insight

Water at any position depends on the minimum of the tallest bars on its left and right. By processing from the shorter side, you always know one bound is satisfied.

Step-by-step

1Initialize left = 0, right = n-1, maxLeft = 0, maxRight = 0, result = 0
2While left < right, compare height[left] and height[right]
3If height[left] < height[right]: process left side
4 Update maxLeft, add (maxLeft - height[left]) to result, move left++
5Else: process right side
6 Update maxRight, add (maxRight - height[right]) to result, move right--

Pseudocode

left = 0, right = n - 1
maxLeft = 0, maxRight = 0, result = 0
while left < right:
    if height[left] < height[right]:
        maxLeft = max(maxLeft, height[left])
        result += maxLeft - height[left]
        left++
    else:
        maxRight = max(maxRight, height[right])
        result += maxRight - height[right]
        right--
return result

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Master this pattern with YeetCode

Practice Trapping Rain Water and similar Two Pointers problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Container With Most Water