Trapping Rain Water
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:
0,1,0,2,1,0,1,3,2,1,2,1
6
- We initialize two pointers, one at the start and one at the end of the elevation map, to track the maximum height of the left and right bars.
- We compare the heights of the bars at the current positions of the two pointers and move the pointer with the smaller height towards the other end, calculating the trapped water as heightmax​−heightcurrent​, where heightmax​ is the maximum height of the left or right bar.
- At each step, we update the maximum height of the left or right bar if the current bar is higher, ensuring that we capture the maximum amount of trapped water.
- The total trapped water is the sum of the trapped water at each position, resulting in a total of 6 units of water trapped between the bars.
Constraints:
- 1 <= len(height) <= 2 * 10^4
- 0 <= height[i] <= 10^5
Background Knowledge
The "Trapping Rain Water" problem is a classic example of a dynamic programming problem, which involves breaking down complex problems into simpler sub-problems and solving each sub-problem only once. In this case, we need to understand how to calculate the amount of water that can be trapped between bars of different heights. The key concept here is to find the maximum height of the bars on both the left and right sides of each bar, as this will determine the amount of water that can be trapped.
To approach this problem, we need to have a good understanding of arrays and how to iterate through them. We also need to understand how to keep track of the maximum height of the bars on both the left and right sides of each bar. This can be achieved using two pointers, one starting from the left and one from the right, and moving towards the center. The height of each bar will play a crucial role in determining the amount of water that can be trapped.
The problem can be visualized as a series of bars with different heights, where the width of each bar is 1. The goal is to calculate the total amount of water that can be trapped between these bars after raining. This requires us to think about how the water will flow and where it will accumulate. We need to consider the local maxima and local minima of the bars, as these will determine the amount of water that can be trapped.
Algorithm/Approach
The general approach to solving this problem involves using a two-pointer technique, where we start from both ends of the array and move towards the center. This allows us to keep track of the maximum height of the bars on both the left and right sides of each bar. We can use dynamic programming to store the maximum height of the bars on both sides and calculate the amount of water that can be trapped.
Step-by-Step Strategy
To implement the solution, we can follow these steps:
- Initialize two pointers, one at the beginning and one at the end of the array.
- Initialize two variables to keep track of the maximum height of the bars on both the left and right sides.
- Iterate through the array, moving the pointers towards the center.
- At each step, update the maximum height of the bars on both sides and calculate the amount of water that can be trapped.
- Add the trapped water to the total amount of water that can be trapped.
Common Pitfalls
When implementing the solution, we need to watch out for the following:
- Make sure to update the maximum height of the bars on both sides correctly.
- Be careful when calculating the amount of water that can be trapped, as this depends on the minimum of the maximum heights on both sides.
- Avoid using unnecessary variables or data structures that can increase the time and space complexity of the solution.
Time & Space Complexity
The expected time complexity of the solution is O(n), where n is the number of bars in the elevation map. This is because we only need to iterate through the array once to calculate the amount of water that can be trapped. The expected space complexity is O(1), as we only need to use a constant amount of space to store the maximum height of the bars on both sides and the total amount of water that can be trapped.