Interview Problem | Trapping rain water problem

Suppose there is an of non-negative numbers and these numbers represent the height of bars. The problem is to compute the amount to water that can be stored.

input → int arr[] = new int[]{1,0,3,1,2,3,1,0};

output → 4

according to above array we can store 1 unit of water between 1 and 3, and 1 uint of water between 3 and 2.

lets write a program to compute the answer.

public static void main(String[] args){

int arr[] = new int[]{1,0,3,1,2,3,1,0};

int heightFromLeft[] = new int[n];
int heightFromRight[] = new int[n];
int waterUnit = 0;
heightFromLeft[0] = arr[0];

//calculating the max height from left
for (int i = 1; i < n; i++) {
heightFromLeft[i] = Math.max(heightFromLeft[i — 1], arr[i]);
}

heightFromRight[n — 1] = arr[n — 1];

//calculating the max height from Right
for (int i = n — 2; i >= 0; i — ) {
heightFromRight[i] = Math.max(heightFromRight[i + 1], arr[i]);
}

//minimum of(left max height , right max height) - current height
for (int i = 0; i < n; i++) {
waterUnit += Math.min(heightFromLeft[i], heightFromRight[i]) — arr[i];
}
System.out.println(waterUnit);

}