Trapping Rain Water Problem in Java
Trapping rainwater is a classic problem in computer science and mathematics that involves calculating the amount of water that can be trapped between a set of bars. In this article, we will explore how to solve this problem in Java with example program.
Problem Statement
Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
For example
given [0,1,0,2,1,0,1,3,2,1,2,1],
Output: 6
Representing the amount of water that can be trapped between the bars.
Solution to The Problem
The solution to this problem involves calculating the maximum height of bars to the left and right of each bar and then subtracting the height of the current bar to get the water trapped at that point.
Let's look at the implementation of this algorithm in Java.
Trapping Rainwater using Brute Force Approach
Filename: TrappingRainwater.java
public class TrappingRainwater {
public static int trap(int[] height) {
int n = height.length;
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int left = height[i];
for (int j = 0; j < i; j++) {
left = Math.max(left, height[j]);
}
int right = height[i];
for (int j = i + 1; j < n; j++) {
right = Math.max(right, height[j]);
}
ans += Math.min(left, right) - height[i];
}
return ans;
}
public static void main(String[] args) {
int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println("Amount of water trapped: " + trap(height));
}
}
Output:
Amount of water trapped: 6
In the above program, we iterate through each bar and calculate the maximum height of bars to the left and right of it using two separate loops. We then subtract the height of the current bar from the minimum of the left and right maximums to get the water trapped at that point. Finally, we add up all the trapped water to get the total trapped water.
Trapping Rainwater using Two-Pointer Approach
Filename: TrappingRainwater.java
public class TrappingRainwater {
public static int trap(int[] height) {
int n = height.length;
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int ans = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
ans += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
ans += rightMax - height[right];
}
right--;
}
}
return ans;
}
public static void main(String[] args) {
int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println("Amount of water trapped: " + trap(height));
}
}
Output:
Amount of water trapped: 6
In the above program, we use a two-pointer approach where we initialize two pointers, one at the beginning and one at the end of the array. We then calculate the maximum height of bars to the left and right of the two pointers and move the pointer with the lower height towards the other pointer.
We maintain leftMax and rightMax to keep track of the maximum height of bars to the left and right of the pointers respectively. If the height at the left pointer is less than the height at the right pointer, we check if the height at the left pointer is greater than or equal to leftMax. If it is, we update leftMax, else we add the trapped water at the left pointer to the ans variable. Similarly, if the height at the right pointer is less than the height at the left pointer, we check if the height at the right pointer is greater than or equal to rightMax. If it is, we update rightMax, else we add the trapped water at the right pointer to the ans variable.
As we can see, both programs produce the same output for the given input array. Both approaches have a time complexity of O(n^2) and O(n) respectively, where n is the length of the input array. The two-pointer approach is more efficient than the brute-force approach, and we should prefer it when the input size is large.
In this article, we explored how to solve the trapping rainwater problem in Java using two different approaches. The brute-force approach involves iterating through each bar and calculating the maximum height of bars to the left and right of it. The two-pointer approach involves initializing two pointers and moving the pointer with the lower height towards the other pointer while maintaining the maximum height of bars to the left and right of the pointers.