LeetCode 42 Trapping Rain Water - Example and Complexity Analysis

Trace height = [4, 2, 0, 3, 2, 5].

Initialize: left = 0, right = 5, leftMax = 0, rightMax = 0, water = 0.

height[0] = 4 < height[5] = 5. Process left.

• height[0] = 4 >= leftMax = 0. Update leftMax = 4. No water. Move left.

height[1] = 2 < height[5] = 5. Process left.

• height[1] = 2 < leftMax = 4. Water = 4 - 2 = 2. Move left.

height[2] = 0 < height[5] = 5. Process left.

• height[2] = 0 < leftMax = 4. Water += 4 - 0 = 4. Total = 6. Move left.

height[3] = 3 < height[5] = 5. Process left.

• height[3] = 3 < leftMax = 4. Water += 4 - 3 = 1. Total = 7. Move left.

Continue until pointers meet. Final answer: 9.

Each position visited once. That's $O(n)$ time. Only tracking four variables. That's $O(1)$ space.