java - trapping rain water elevations is array -

i going through problem in 1 of exam paper , found 1 solution in answer book. not able understand algorithm behind it. can explain me how algorithm works?

given n non-negative integers representing elevation map width of each bar 1, compute how water able trap after raining.

for example, given input

[0,1,0,2,1,0,1,3,2,1,2,1]  

the return value be

6 

solution per answer book this

public class solution {     public int trap(int[] height) {         if (height.length <=2 )             return 0;         int h = 0, sum = 0, = 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

wodosc nice enough draw diagram of elevations , trapped water. water can trapped between 2 higher elevations.

what did run code , output results can see how trapped water calculated. code starts @ both ends of "mountain" range. whichever end lower moved closer center.

in case 2 ends same height, right end moved closer center. move left end closer center instead.

the first column height , index of elevations on left. second column height , index of elevations on right.

the third column maximum minimum height. in other words, maximum height of left or right, whichever maximum smaller. number important determine local water level.

the fourth column sum.

follow along diagram , can see how 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 code. putting print , println statements in appropriate places can understand code 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, = 0, j = height.length - 1;          while (i < j) {             system.out.print(height[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;     }  }