LeetCode Study Note | Problem 42: Trapping Rain Water

🔍 Problem Description

Given a non-negative integer array height[] representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining.

💡 Core Idea: Two-Pointer Technique

📌 Water at any index i is calculated as:

water[i] = min(left_max, right_max) - height[i]

Where:

• left_max: The highest bar to the left of index i

• right_max: The highest bar to the right of index i

🧠 Intuition Behind the Algorithm

Use two pointers:

• left starting from the beginning

• right starting from the end

Maintain two variables:

• left_max: max height seen so far from the left

• right_max: max height seen so far from the right

At each step, move the pointer pointing to the shorter side. This ensures we only process positions where we can safely determine the trapped water based on the known max height on the opposite side.

❓ Why Compare 

height[left] < height[right]?

• The water trapped depends on the shorter boundary.

• If the left side is shorter, we are certain that the right boundary is tall enough.

• This allows us to calculate water at left safely using only left_max.

If we process the taller side first, we may not yet know whether the opposite side is high enough, and risk calculating incorrect water.

🔄 Step-by-Step Algorithm

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}

🧪 What If You Process the Wrong Side?

If you always move right even when left is shorter (or vice versa), you risk:

• Using an unknown max on the opposite side

• Calculating water with incomplete information

• Underestimating or overestimating water trapped

Only the shorter side gives you enough certainty to safely calculate water at that position.

📊 Example

height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6

Visual Representation:

          _
      _  | |
_   | | | | |
|_|_|_|_|_|_|_
0 1 0 2 1 0 1 3 2 1 2 1

Water is trapped in the valleys between taller bars.

⏱ Complexity

Only a single pass is made with constant extra space.