LeetCode 42: Trapping Rain Water — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Hard — Two Pointers | Array | Dynamic Programming | Stack

The Problem

Given an elevation map represented by an array of non-negative integers, calculate how much water can be trapped after raining.

Approach

Uses two pointers starting from both ends of the array, tracking the maximum heights seen so far from left and right. Water can be trapped at a position if there are higher bars on both sides, so we calculate trapped water by subtracting current height from the maximum height on the side with the smaller maximum.

Time: O(n) · Space: O(1)

Code

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_left, max_right = 0, 0
        trapped_water = 0

        while left < right:
            if height[left] <= height[right]:
                if height[left] >= max_left:
                    max_left = height[left]
                else:
                    trapped_water += max_left - height[left]
                left += 1
            else:
                if height[right] >= max_right:
                    max_right = height[right]
                else:
                    trapped_water += max_right - height[right]
                right -= 1

        return trapped_water