Trapping Rain Water
Problem Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Example 2:
Constraints:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
Solve it on LeetCode
Approaches
1. Brute Force
The brute force approach involves iterating over each element in the height array and for each element, calculating the maximum water that can be trapped above it by determining the highest bars to its left and right. This is done in three loops: one for the current index, and two for finding the left and right max bars.
Intuition:
- For each bar, calculate the maximum height of the bars to the left and right.
- The water level on top of the current bar is the minimum of these two heights minus the height of the current bar.
- Sum this for each bar.
Code:
- Time Complexity: O(n^2) because of the nested loops for calculating left and right max heights for each element.
- Space Complexity: O(1) since we are using constant extra space.
2. Dynamic Programming
The dynamic programming approach involves precomputing the maximum height to the left and right of each element using separate arrays. This eliminates the need for nested loops, as in the brute force approach.
Intuition:
- Use two arrays,
leftMaxandrightMax. leftMax[i]stores the maximum height from the start to indexi.rightMax[i]stores the maximum height from indexito the end.- Calculate the trapped water for each element as before, but use precomputed arrays.
Code:
- Time Complexity: O(n) because we are making three separate passes over the array.
- Space Complexity: O(n) due to the additional
leftMaxandrightMaxarrays used.
3. Two Pointers
The two-pointers technique improves upon the dynamic programming solution by using two pointers that traverse the height array from both ends. It uses variables to store current left and right max heights, allowing us to calculate the trapped water more efficiently without additional space.
Intuition:
- Initialize two pointers,
leftat the start andrightat the end of the array. - Maintain two variables
leftMaxandrightMaxfor the maximum heights encountered from the left and right, respectively. - Move the pointers towards each other, updating trapped water based on which of
leftMaxandrightMaxis smaller.
Code:
- Time Complexity: O(n) as we traverse the height array only once with the two pointers.
- Space Complexity: O(1) because we use only constant extra space.