trapping rain water elevations is array

Question

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

Answer 1

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;
    }

}

Answer 2

I know that probably it's not the best way to represent it graphically, but you can imagine the situation as the following figure:

Where the red bars are the terrain (with elevations according to the array of your example), and the blue bars are the water that can be "trapped" into the "valleys" of the terrain.

Simplifying, the algorithm loops all the bar left-to-right (if left is smaller) or right-to-left (if right is smaller), the variable h stores the maximum height found during each step of the loop, because the water can not be higher than the maximum height of the terrains, and to know how much water can be trapped, it sums the differences between the height of the water (maximum height h) and the elevation of the terrain on a specific point, to get the actual quantity of water.