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

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