Can You Trap the Sky? Understanding the Trapping Rain Water Problem
Imagine a cityscape defined by buildings of varying heights. When it rains, water gets trapped in the depressions formed between these buildings. The "Trapping Rain Water" problem asks us to calculate the total amount of rainwater that can be trapped in such a scenario, given an array representing the height of the buildings (where each element's index corresponds to a building's position and the value is its height).
This might seem like a simple visualization, but translating it into an algorithm that efficiently calculates the trapped water is a classic interview question that tests your understanding of array manipulation, logical reasoning, and potentially dynamic programming or two-pointer techniques.
Let's dive deeper into the problem and explore a common and efficient approach to solve it using Java.
Understanding the Conditions for Trapping Water
Water can only be trapped if there are higher bars to its left and right. Think of it like creating a container. The height of the trapped water at any given position is limited by the shorter of the tallest bars to its left and right. The actual height of the bar at the current position then determines how much water can be held above it.
Visual Example:
Consider the height array: [0, 1, 0, 2, 1, 0, 3, 1, 0, 1, 2]
If we visualize this:
_
| |
| | _
|_| | | _
| |__| |_ _| |
|_|_|_|_|_|_|_|
0 1 0 2 1 0 3 1 0 1 2
The water trapped would look something like this (represented by '~'):
_
| |
|~| _
|_|~~| |~~~_
| |__| |_~| |
|_|_|_|_|_|_|_|
0 1 0 2 1 0 3 1 0 1 2
Our goal is to calculate the total volume of this trapped water.
A Two-Pointer Approach in Java
One of the most efficient ways to solve this problem is using a two-pointer approach. Here's how it works:
* Initialize Pointers: We'll have two pointers, left starting at the beginning of the array (index 0) and right starting at the end of the array (index n-1, where n is the length of the array).
* Maintain Maximum Heights: We'll also need to keep track of the maximum height encountered so far from the left (maxLeft) and the maximum height encountered so far from the right (maxRight). Initialize both to 0.
* Iterate and Compare: We'll move the pointers towards each other until they meet (left < right). In each step:
* Compare Heights: Compare the height at the left pointer with the height at the right pointer.
* Move the Smaller Pointer:
* If heights\[left] is less than heights\[right], it means the potential for trapping water at the left position is limited by maxRight (the tallest bar seen so far from the right).
* If heights\[left] is greater than or equal to maxLeft, it means this bar itself is now the tallest we've seen from the left, so update maxLeft = heights\[left].
* Otherwise, if heights\[left] is smaller than maxLeft, it means we can trap water at this position. The amount of water trapped is maxLeft - heights\[left]. Add this to our total trapped water.
* Increment the left pointer.
* If heights\[right] is less than or equal to heights\[left], the logic is symmetric. The potential for trapping water at the right position is limited by maxLeft.
* If heights\[right] is greater than or equal to maxRight, update maxRight = heights\[right].
* Otherwise, add maxRight - heights\[right] to the total trapped water.
* Decrement the right pointer.
* Return Total Water: Once the left and right pointers meet, we will have iterated through all the possible positions where water can be trapped, and the accumulated value will be the total trapped rainwater.
Java Implementation:
Here's the Java code implementing the two-pointer approach:
class TrappingRainWater {
public int trap(int[] height) {
if (height == null || height.length < 3) {
return 0; // Cannot trap water with less than 3 bars
}
int left = 0;
int right = height.length - 1;
int maxLeft = 0;
int maxRight = 0;
int trappedWater = 0;
while (left < right) {
if (heights\[left] < heights\[right]) {
if (heights\[left] >= maxLeft) {
maxLeft = heights\[left];
} else {
trappedWater += maxLeft - heights\[left];
}
left++;
} else {
if (heights\[right] >= maxRight) {
maxRight = heights\[right];
} else {
trappedWater += maxRight - heights\[right];
}
right--;
}
}
return trappedWater;
}
public static void main(String[] args) {
TrappingRainWater solution = new TrappingRainWater();
int[] heights1 = {0, 1, 0, 2, 1, 0, 3, 1, 0, 1, 2};
System.out.println("Trapped water for heights1: " + solution.trap(heights1)); // Output: 6
int[] heights2 = {4, 2, 0, 3, 2, 5};
System.out.println("Trapped water for heights2: " + solution.trap(heights2)); // Output: 9
int[] heights3 = {2, 0, 2};
System.out.println("Trapped water for heights3: " + solution.trap(heights3)); // Output: 2
}
}
Time and Space Complexity:
* Time Complexity: O(n), where n is the number of bars (length of the height array). We iterate through the array at most once with our two pointers.
* Space Complexity: O(1), as we are only using a constant amount of extra space for our pointers and maximum height variables.
Alternative Approaches (Briefly Mentioned):
While the two-pointer approach is efficient, the Trapping Rain Water problem can also be solved using:
* Dynamic Programming: You can pre-calculate the maximum height to the left and right of each bar and then iterate through the array to calculate the trapped water at each position. This approach also has a time complexity of O(n) but requires O(n) extra space for the two auxiliary arrays.
* Stack-Based Approach: Using a stack, you can keep track of decreasing bar heights and calculate trapped water when a taller bar is encountered. This approach can also achieve O(n) time complexity.
Conclusion:
The Trapping Rain Water problem is a great example of how a seemingly intuitive problem can lead to interesting algorithmic challenges. The two-pointer approach provides an elegant and efficient solution, showcasing the power of carefully managing pointers to solve array-based problems. Understanding the underlying logic of how water gets trapped and considering the limiting factors (the tallest bars on either side) is key to grasping the solution. So, the next time you see a cityscape after a downpour, remember the logic behind calculating the trapped "sky" between the buildings!
No comments:
Post a Comment