Trapping Rain Water — Two Pointer Visual

LC 42 — Trapping Rain Water

Input: [4, 2, 0, 3, 2, 5]

---

Step 1 — Visualize the Heights

        idx:  0    1    2    3    4    5
     height:  4    2    0    3    2    5

 5 |              |              |  █  |
 4 |  █  |        |              |  █  |
 3 |  █  |        |  █  |        |  █  |
 2 |  █  |  █  |  █  |  █  |        |  █  |
 1 |  █  |  █  |  █  |  █  |  █  |  █  |
   +------+------+------+------+------+------+
      0      1      2      3      4      5

---

Step 2 — Add Water

Water at each index = min(maxLeft, maxRight) - height[i]

        idx:  0    1    2    3    4    5
     height:  4    2    0    3    2    5

 5 |              |              |  █  |
 4 |  █  |  ≈  |  ≈  |  ≈  |  ≈  |  █  |   <- bounded by maxLeft=4
 3 |  █  |  ≈  |  ≈  |  █  |  ≈  |  █  |
 2 |  █  |  █  |  ≈  |  █  |  █  |  █  |
 1 |  █  |  █  |  ≈  |  █  |  █  |  █  |
   +------+------+------+------+------+------+
      0      1      2      3      4      5

  █ = wall    ≈ = trapped water

Total = 9

---

Step 3 — Two Pointer Walkthrough

Rule: process whichever side has the smaller max — that side is the bottleneck.

Initial:
  left=0, right=5, maxLeft=0, maxRight=0, ans=0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: maxLeft(0) <= maxRight(0) → process LEFT
  maxLeft = max(0, height[0]=4) = 4
  water   = 4 - 4 = 0
  left → 1
  ans = 0

  [  L              R  ]
   4    2    0    3    2    5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 2: maxLeft(4) > maxRight(0) → process RIGHT
  maxRight = max(0, height[5]=5) = 5
  water    = 5 - 5 = 0
  right → 4
  ans = 0

  [       L         R  ]
   4    2    0    3    2    5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 3: maxLeft(4) <= maxRight(5) → process LEFT
  maxLeft = max(4, height[1]=2) = 4
  water   = 4 - 2 = 2   ← water trapped!
  left → 2
  ans = 2

  [            L    R  ]
   4    2    0    3    2    5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 4: maxLeft(4) <= maxRight(5) → process LEFT
  maxLeft = max(4, height[2]=0) = 4
  water   = 4 - 0 = 4   ← water trapped!
  left → 3
  ans = 6

  [                 LR ]
   4    2    0    3    2    5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 5: maxLeft(4) <= maxRight(5) → process LEFT
  maxLeft = max(4, height[3]=3) = 4
  water   = 4 - 3 = 1   ← water trapped!
  left → 4
  ans = 7

  [                    LR]
   4    2    0    3    2    5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 6: left == right == 4  (use <= condition)
  maxLeft(4) <= maxRight(5) → process LEFT
  maxLeft = max(4, height[4]=2) = 4
  water   = 4 - 2 = 2   ← water trapped!
  left → 5
  ans = 9

  left(5) > right(4) → EXIT

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Final Answer: 9 ✅

---

Why the smaller side is always safe to process

At any point:

   maxLeft              maxRight
     │                     │
     ▼                     ▼
  ┌──────┐             ┌──────┐
  │      │   ... X ... │      │
  └──────┘             └──────┘
   left                 right

If maxLeft <= maxRight:
  - True right max for position `left` >= maxRight >= maxLeft
  - So min(maxLeft, trueRightMax) = maxLeft  ← always
  - You don't need to know what's on the right anymore
  - Safe to compute: water = maxLeft - height[left]

Same logic in reverse when maxRight < maxLeft.

---

Final Code

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        maxLeft, maxRight = 0, 0
        ans = 0
        while left <= right:          # <= to include meeting point
            if maxLeft <= maxRight:
                maxLeft = max(maxLeft, height[left])
                ans += maxLeft - height[left]
                left += 1
            else:
                maxRight = max(maxRight, height[right])
                ans += maxRight - height[right]
                right -= 1
        return ans

TC: O(n) | SC: O(1)