Trapping Rain Water - Video Solutions

Problem Overview: You are given an array where each element represents the height of a vertical bar in an elevation map. After rain, water collects in the gaps between bars. The task is to compute how many total units of water remain trapped after the rain.

Approach 1: Two-Pass Dynamic Programming (O(n) time, O(n) space)

This approach precomputes the tallest bar on the left and right of every index. Create two arrays: leftMax[i] stores the maximum height from the start up to i, and rightMax[i] stores the maximum height from the end down to i. The water trapped above index i is min(leftMax[i], rightMax[i]) - height[i]. Iterate through the array once to fill leftMax, once for rightMax, and once more to accumulate trapped water. Time complexity is O(n) and space complexity is O(n). This method is straightforward and a good way to understand the core insight that water level depends on the shorter boundary.

This problem is a classic example involving arrays and boundary precomputation using dynamic programming style prefix/suffix information.

Approach 2: Two-Pointer Technique (O(n) time, O(1) space)

The optimal solution eliminates the extra arrays by processing from both ends simultaneously. Maintain two pointers: left at the start and right at the end. Track the highest bars seen so far from both directions using leftMax and rightMax. If height[left] < height[right], the trapped water depends only on the left side because the right boundary is guaranteed to be taller. Update leftMax or accumulate water, then move left. Otherwise process the right side similarly. Each index is visited once, producing O(n) time and O(1) extra space. This technique relies on the observation that the smaller boundary determines the water level.

This strategy is a standard pattern when solving problems with two pointers moving toward each other while maintaining partial state.

Approach 3: Monotonic Stack (O(n) time, O(n) space)

A stack-based solution processes bars while maintaining a decreasing stack of indices. When the current bar becomes taller than the bar at the top of the stack, a container boundary is discovered. Pop the stack to form a valley, compute the bounded height using the difference between the current bar and the new stack top, and multiply by the horizontal distance. Each index enters and leaves the stack once, so the time complexity remains O(n) with O(n) auxiliary space. This approach highlights how trapped water forms between two boundaries and is often discussed when learning monotonic stacks.

Recommended for interviews: Interviewers typically expect the two-pointer solution. The dynamic programming version clearly demonstrates the core insight and is a good stepping stone, but the two-pointer technique proves you can reduce memory while maintaining linear time.