Amazon question: Calculate total amount of rain water trapped between the towers.

This question was asked by amazon , to calculate the amount of water trapped between the  towers with the help of given array which consists of height of the each tower.

For example: input : int tower = {4,2,3,5,2,3,4,5};

For the above example , the output, i.e.Total amount of the water is the summation of water stored in the tower 2,3,5,6 and tower 7. i.e (2+1+3+2+1=9).

The logic should work for all the scenario, means tallest tower can be located anywhere, it can be first, last or in any position. Lets see the below towers.

Example 2:- input: int tower = {5,0,5,2,5,3,4,5}

Logic :-
  
The logic would be, for every tower calculate the highest height of the tower from left and highest height of tower from the right and then use minimum height of these two tower, to calculate the amount of water. For example:- 

From the above figure 1:- For tower 2, highest height of the tower from left is tower 1(4) and highest height of the tower from right is tower 4(5), then take minimum height of this two tower(4), and subtract the height of tower 2(2) from this minimum tower(4), this will be the amount of water trapped for the tower 2. The output will be (4-2) = 2. Repeat the above step for all the tower and add the output of water trapped for each tower. This will be the total amount of rain trapped between the towers.


Algorithm:-

Step 1: Declare left and right array to store the highest height from left and right side of the each tower and waterAmount to calculate the total amount of water trapped between the towers.
Step 2: Traverse the input array(height of all the towers) and  calculate the maximum height of tower from the left and from the right of each tower and assign to left and right array respectively.
Step 3: Again traverse the input array and calculate the amount of trapped water for all the tower and add the result to waterAmount value.

Code:-

import java.util.Arrays;
public class RainwaterStorage{

public static void main(String[] args) {
int tower[] = {4,2,3,5,2,3,4,5}; // height of all the tower
System.out.println(findWaterAmount(tower, tower.length));
}

public static int findWaterAmount(int tower[], int count)
{
   int left[] = new int[count];
   int right[] = new int[count];
   int waterAmount = 0;   
   // Fill left array (contain maximum height tower value from the left of each tower)
   left[0] = tower[0];
   for (int i = 1; i < count; i++)
      left[i] = Math.max(left[i-1], tower[i]);

   // Fill right array (contain maximum height tower value from the right of each tower)
   right[count-1] = tower[count-1];
   for (int i = count-2; i >= 0; i--)
      right[i] = Math.max(right[i+1], tower[i]);

   // below code is to find the amount of trapped water for all the tower and add the result to waterAmount value. 
   for (int i = 0; i < n; i++) 
       waterAmount+= Math.min(left[i],right[i]) - tower[i];

   return waterAmount;
}
}

Output:-
9

Performance:- 
Time Complexity: O(n). Traversing all the elements in array
Auxiliary Space: O(n). Additional aray to store maximum value of the tower from the left and from right.

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog