In this post we will solve the LeetCode 42. Trapping Rain Water problem using the Java programming language and the VSCode IDE on a Windows computer. The simplest approach is to develop the code on the online IDE provided by LeetCode.
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. Constraints: o n == height.length o 1 <= n <= 2 * 10^4 o 0 <= height[i] <= 10^5 Related Topics: * Array * Two Pointers o Dynamic Programming o Stack o Monotonic Stack
The diagram on the LeetCode page is very useful to get the general idea of what the problem is. It also helps to draw the diagram on a piece of paper and figure out an approach. We need to calculate the amount of water on each cell and add them together to get our result. The trick is in how we implement the task.
I will be solving the problem on my computer and then copying the solution to LeetCode for evaluation. I will be developing a simple test scaffold to collect the input data, populate the array, call the function of interest and display the output. Please note that the test code IS NOT PART OF THE SOLUTION!
public int trap(int[] height) {
}
The signature for the function of interest matches very well the problem requirements. We are given in int[] with the heights of the bars and we need to return the amount of collected rain.
0,1,0,2,1,0,1,3,2,1,2,1 main <<< height: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] <<< n: 12 <<< left: 1 right: 11 waterTrapped: 0 <<< left: 1 right: 10 waterTrapped: 0 <<< left: 2 right: 10 waterTrapped: 1 <<< left: 3 right: 10 waterTrapped: 1 <<< left: 3 right: 9 waterTrapped: 2 <<< left: 3 right: 8 waterTrapped: 2 <<< left: 3 right: 7 waterTrapped: 2 <<< left: 4 right: 7 waterTrapped: 3 <<< left: 5 right: 7 waterTrapped: 5 <<< left: 6 right: 7 waterTrapped: 6 <<< left: 7 right: 7 waterTrapped: 6 main <<< trap0: 6 <<< n: 12 <<< maxLeft: [0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] <<< maxRight: [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0] <<< minLR: [0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 1, 0] <<< i: 2 water: 1 <<< i: 4 water: 1 <<< i: 5 water: 2 <<< i: 6 water: 1 <<< i: 9 water: 1 main <<< trap: 6 4,2,0,3,2,5 main <<< height: [4, 2, 0, 3, 2, 5] <<< n: 6 <<< left: 1 right: 5 waterTrapped: 2 <<< left: 2 right: 5 waterTrapped: 6 <<< left: 3 right: 5 waterTrapped: 7 <<< left: 4 right: 5 waterTrapped: 9 <<< left: 5 right: 5 waterTrapped: 9 main <<< trap0: 9 <<< n: 6 <<< maxLeft: [0, 4, 4, 4, 4, 4] <<< maxRight: [5, 5, 5, 5, 5, 0] <<< minLR: [0, 4, 4, 4, 4, 0] <<< i: 1 water: 2 <<< i: 2 water: 4 <<< i: 3 water: 1 <<< i: 4 water: 2 main <<< trap: 9
The test cases are separated by two blank lines.
The first line in each test case holds the values for the int[] `height`. Our test code seems to read the input line, declare, populate and display the int[] `height`. This is done to make sure all is well before calling the function of interest.
It seems that we have two implementations of the function of interest.
Our test scaffold calls the implementations and displays the associated results. The messages in between are used to provide us information on how the code is progressing. This helps to understand the algorithm and to debug the code during development.
/**
* Test scaffold.
* !!! NOT PART OF THE SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
var br = new BufferedReader(new InputStreamReader(System.in));
// **** read height int[] array ****
int[] height = Arrays.stream(br.readLine().trim().split(","))
.map(s -> s.trim())
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< height: " + Arrays.toString(height));
// **** call function of interest and display output ****
System.out.println("main <<< trap0: " + trap0(height));
// **** call function of interest and display output ****
System.out.println("main <<< trap: " + trap(height));
}
Our test scaffold is quite simple. It reads the input line, populates the int[] `height` (perhaps it should have been named `heights`) and then calls the first implementation of the function of interest. The result is displayed. The same approach is used with the second implementation. Please note that the test code IS NOT PART OF THE SOLUTION!
Key concept: water = max(maxLeft, maxRight) - height[i];
The key concept to solve the problem in both implementations is to determine the statement to calculate the amount of water in each bar in the `height` int[] array.
/**
* 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.
*
* Runtime: O(n) - Space: O(n)
*
* Runtime: 1 ms, faster than 92.42% of Java online submissions.
* Memory Usage: 38.8 MB, less than 64.52% of Java online submissions.
*
* 320 / 320 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 38.8 MB
*/
static public int trap(int[] height) {
// **** initialization ****
int n = height.length;
// **** sanity check (no rain can be collected) ****
if (n <= 2) return 0;
// **** ****
int waterTrapped = 0;
int[] maxLeft = new int[n];
int[] maxRight = new int[n];
int[] minLR = new int[n];
int ml = 0;
int mr = 0;
// ???? ????
System.out.println("<<< n: " + n);
// **** populate maxLeft - O(n) ****
for (int i = 0; i < n; i++) {
// **** ****
if (i == 0) {
maxLeft[i] = height[i];
ml = 0;
}
// **** populate maxLeft ****
maxLeft[i] = ml;
// **** update ml ****
if (ml < height[i])
ml = height[i];
}
// ???? ????
System.out.println("<<< maxLeft: " + Arrays.toString(maxLeft));
// **** populate maxRight and min(L,R) - O(n) ****
for (int i = n - 1; i >= 0; i--) {
// **** ****
if (i == n - 1) {
maxRight[i] = height[i];
mr = 0;
}
// **** populate maxRight ****
maxRight[i] = mr;
// **** update mr ****
if (mr < height[i])
mr = height[i];
// **** poulate minLR ****
minLR[i] = Math.min(maxLeft[i], maxRight[i]);
}
// ???? ????
System.out.println("<<< maxRight: " + Arrays.toString(maxRight));
System.out.println("<<< minLR: " + Arrays.toString(minLR));
// **** compute maxWater - O(n) ****
for (int i = 0; i < n; i++) {
// **** water in this cell (key computation) ****
int water = minLR[i] - height[i];
// **** increment water trapped (if needed) ****
if (water > 0) {
// ???? ????
System.out.println("<<< i: " + i + " water: " + water);
// **** increment water trapped ****
waterTrapped += water;
}
}
// **** return water trapped ****
return waterTrapped;
}
This is the first implementation of the function of interest.
We start by performing a sanity check followed by an initialization step in which we declare three int[] arrays. The `maxLeft` array will hold the maximum left value seen at each bar when moving from left to right. The `maxRight` array will hold the maximum right value encountered at each bar when moving from right to left. The `minLR` int[] array will hold the minimum value of `maxLeft` and `maxRight` for each bar. This will become clearer as we look at the rest of the code.
In the first loop we populate the `maxLeft` int[] array.
In the second loop we populate the values in the `maxRight` int[] array and since we already have the values of `maxLeft` we are also able to fill the values of the `minLR` int[] array.
In the last loop we traverse the `height` int[] array generating the amount of water at each bar. If the amount is larger than zero we add the `water` value to the `waterTrapped` variable.
When all is said and done we returned the amount of water trapped.
For execution statistics please look at the comments section of this function in the code we just finished looking at.
/**
* 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.
*
* Runtime: O(n) - Space: O(1)
*
* Runtime: 9 ms, faster than 9.07% of Java online submissions.
* Memory Usage: 42.2 MB, less than 17.46% of Java online submissions.
*
* 320 / 320 test cases passed.
* Status: Accepted
* Runtime: 9 ms
* Memory Usage: 42.2 MB
*/
static public int trap0(int[] height) {
// **** set n ****
int n = height.length;
// ???? ????
System.out.println("<<< n: " + n);
// **** sanity check (no rain can be collected) ****
if (n <= 2) return 0;
// **** initialization ****
int waterTrapped = 0;
int left = 0;
int right = n - 1;
int leftMax = height[left];
int rightMax = height[right];
// **** traverse height array - O(n) ****
while (left < right) {
// **** update left or right ****
if (leftMax < rightMax) {
// **** update left pointer ****
left++;
// **** update left max value ****
leftMax = Math.max(leftMax, height[left]);
// **** compute collected water increment ****
waterTrapped += leftMax - height[left];
} else {
// **** update right pointer ****
right--;
// **** update right max value ****
rightMax = Math.max(rightMax, height[right]);
// **** compute collected water increment ****
waterTrapped += rightMax - height[right];
}
// ???? ????
System.out.println("<<< left: " + left + " right: " + right + " waterTrapped: " + waterTrapped);
}
// **** return water trapped ****
return waterTrapped;
}
The approach for this function is similar to the one used in the previous implementation. The idea is to determine if we can eliminate the use of the three arrays in order to eliminate the space O(n).
We start by performing a sanity check. Note that if we have an array with only two values no water can be collected.
We then declare and initialize some variables.
The while loop is used in conjunction with the `left` and `right` pointers (indices) to provide the information for the left and right ends associated with each `height[i]`.
We have an `if` condition that is used to determine if we increase the `left` pointer or decrease the `right` one.
After updating the pointers we compute the `leftMax` or `rightMax` by using the `height[i]` value.
At this point we only need to compute the amount of water in the current cell and update the contents of the `waterTrapped` variable.
Please take a few moments to compare how this implementation does the same things as the previous one but uses no additional space: O(1).
When all is said and done, the function returns the value in the `waterTrapped` variable.
Please take a look at the comments section of this function in the source code. The execution information is there.
I was surprised to note that without the three int[] arrays the execution time was slower. I believe that results might be somewhat skewed depending on the load at the LeetCode servers. If you have an alternate idea, please leave your comments below.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named TrappingRainWater.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John