Issue
I was going through this problem in one of exam paper and found one solution in answer book. I am not able to understand algorithm behind it. Can anyone explain me how this algorithm works?
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given the input
[0,1,0,2,1,0,1,3,2,1,2,1]
the return value would be
6
Solution as per answer book is this
public class Solution {
public int trap(int[] height) {
if (height.length <=2 )
return 0;
int h = 0, sum = 0, i = 0, j = height.length - 1;
while(i < j)
{
if ( height[i] < height[j] )
{
h = Math.max(h,height[i]);
sum += h - height[i];
i++;
}
else
{
h = Math.max(h,height[j]);
sum += h - height[j];
j--;
}
}
return sum;
}
}
Thanks
Solution
WoDoSc was nice enough to draw a diagram of the elevations and trapped water. The water can only be trapped between two higher elevations.
What I did was run the code and output the results so you can see how the trapped water is calculated. The code starts at both ends of the "mountain" range. Whichever end is lower is moved closer to the center.
In the case where the two ends are the same height, the right end is moved closer to the center. You could move the left end closer to the center instead.
The first column is the height and index of the elevations on the left. The second column is the height and index of the elevations on the right.
The third column is the maximum minimum height. In other words, the maximum height of the left or the right, whichever maximum is smaller. This number is important to determine the local water level.
The fourth column is the sum.
Follow along with the diagram and you can see how the algorithm works.
0,0 1,11 0 0
1,1 1,11 1 0
1,1 2,10 1 0
0,2 2,10 1 1
2,3 2,10 2 1
2,3 1,9 2 2
2,3 2,8 2 2
2,3 3,7 2 2
1,4 3,7 2 3
0,5 3,7 2 5
1,6 3,7 2 6
6
And here's the code. Putting print and println statements in appropriate places can help you understand what the code is doing.
package com.ggl.testing;
public class RainWater implements Runnable {
public static void main(String[] args) {
new RainWater().run();
}
@Override
public void run() {
int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
System.out.println(trap(height));
}
public int trap(int[] height) {
if (height.length <= 2) {
return 0;
}
int h = 0, sum = 0, i = 0, j = height.length - 1;
while (i < j) {
System.out.print(height[i] + "," + i + " " + height[j] + "," + j
+ " ");
if (height[i] < height[j]) {
h = Math.max(h, height[i]);
sum += h - height[i];
i++;
} else {
h = Math.max(h, height[j]);
sum += h - height[j];
j--;
}
System.out.println(h + " " + sum);
}
return sum;
}
}
Answered By - Gilbert Le Blanc
Answer Checked By - Willingham (JavaFixing Volunteer)