Welcome to the Trapping Rain Water problem from LeetCode. In this problem, we are given an array of non-negative integers representing an elevation map. Each integer represents the height of a bar with width 1. Our task is to calculate how much water can be trapped between the bars after it rains. For example, with the heights shown here, water will collect in the gaps between higher bars. The challenge is to efficiently calculate the total volume of trapped water.
Let's examine the brute force approach to solving this problem. For each position in the array, we need to find the maximum height to its left and the maximum height to its right. The amount of water that can be trapped at any position is the minimum of these two maximum heights, minus the height of the current bar. For example, at position 5, the maximum height to its left is 2, and the maximum height to its right is 3. The minimum of these is 2, and since the height at position 5 is 0, the water trapped here is 2 units. This approach has a time complexity of O(n²) because for each position, we need to scan the entire array to find the maximum heights.
A more efficient approach uses dynamic programming. Instead of recalculating the maximum heights for each position, we can precompute them in two arrays: max_left and max_right. The max_left array stores the maximum height from the start up to each position, while the max_right array stores the maximum height from the end down to each position. We fill these arrays in linear time with two passes through the height array. Then, in a third pass, we calculate the water trapped at each position using the same formula: min(max_left, max_right) minus the height. This approach reduces the time complexity to O(n) with O(n) space complexity for the two additional arrays. As shown in the visualization, the green lines represent max_left values and the red lines represent max_right values at each position.
The most efficient solution to the Trapping Rain Water problem uses a two-pointer approach. We maintain two pointers, left and right, starting from the beginning and end of the array respectively. We also track the maximum height seen so far from both sides. The key insight is that the water trapped at any position is determined by the smaller of the two maximum heights. If the maximum height on the left is smaller than the maximum height on the right, we move the left pointer inward; otherwise, we move the right pointer inward. As we move, we update the maximum heights and calculate the water trapped at each position. This approach achieves O(n) time complexity while using only O(1) extra space, making it more memory-efficient than the dynamic programming solution. The animation demonstrates how the pointers move toward each other, calculating trapped water as they go.
Let's summarize what we've learned about solving the Trapping Rain Water problem. First, we understand that the problem asks us to calculate how much water can be trapped between bars of varying heights. We explored three different approaches: The brute force method checks each position individually by finding the maximum heights to its left and right, resulting in O(n²) time complexity with O(1) space. The dynamic programming approach improves time complexity to O(n) by precomputing maximum heights in two arrays, but requires O(n) extra space. Finally, the two-pointer technique achieves the best efficiency with O(n) time and only O(1) space by moving pointers from both ends toward the middle. The key insight across all approaches is that the water trapped at any position depends on the minimum of the maximum heights to its left and right. This problem demonstrates how different algorithmic strategies can solve the same problem with varying efficiency trade-offs.