Water Trapping is a typical problem that is very commonly used by prospective employers to test your analytical or programming skills. And believe me it is quite tricky!!
Water Trapping Problem
For this problem, input is an array with number values representing the heights of vertical bars. The challenge is to return how much water can be stored in the spaces created by a row of vertical bars of equal width.
The logic of the process is to scan from left to right from array storing bars’ heights and calculate the volume of water that can be stored by virtue of the height of current bar compared to other bar making the storage structure.
Algorithm
1. Initialize LEFT = 0 and RIGHT = N-1
2. Initialize LEFT_HEIGHT=0 and RIGHT_HEIGHT=0
3. Repeat steps 4 and 5 while LEFT<RIGHT
4. If HEIGHT[LEFT]<HEIGHT[RIGHT]
a. If HEIGHT[LEFT]>LEFT_HEIGHT then
Update LEFT_HEIGHT= HEIGHT [LEFT]
Else
Update VOL=VOL+ LEFT_HEIGHT- HEIGHT [LEFT]
b. Increment LEFT
5. Else
a. If HEIGHT[RIGHT]>RIGHT_HEIGHT then
Update RIGHT_HEIGHT= HEIGHT [RIGHT]
Else
Update VOL=VOL+ RIGHT_HEIGHT- HEIGHT [RIGHT]
b. Decrement RIGHT
6. Return VOL Description- The algorithm accepts array HEIGHT with N element. Each element of the array represents the height of a vertical bar making the water storage structure.
Let’s assume Array HEIGHT with these values. Indices are from 0 to 6 for values 7 and 9 respectively
| 7 | 5 | 1 | 6 | 5 | 0 | 9 |
The first image shows the initials state of bars for water trapping. The values stored in the HEIGHT array is the heights of the bars in this image
After initialization LEFT=0 , RIGHT=6 and LEFT_HEIGHT=7
In the first iteration LEFT=1, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT [LEFT] (7-5)=2
In the second iteration LEFT=2, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-1)=6
In the third iteration LEFT=3, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-6)=1
In the fourth iteration LEFT=4, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-5)=2
In the fifth iteration LEFT=5, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-0)=7
In the sixth iteration LEFT=6 RIGHT=6 and the volume of water added is 0 since the height of the last bar is greater than height of Left bar. The condition specified in step 3 of the algorithm becomes false and the algorithm is terminated returning the volume of Water Trapping Problem.
Solution with C
#include <stdio.h>
int FindVol(int height[], int num)
{
// Variable declaration
int vol = 0;
//Initialize height variables for two ends
int left_height=0;
int right_height=0;
//Initialize variables for two ends
int start_ind=0;
int end_ind=num-1;
while(start_ind<=end_ind)
{
if (height[start_ind]<height[end_ind])
{
printf("start_ind=%d, end_id=%d\t",start_ind,end_ind);
if (height[start_ind]>left_height)
{
// update Left taller bar
left_height=height[start_ind];
printf("left_height=%d\t",left_height);
}
else
{
// Calculte volume
vol=vol+left_height-height[start_ind];
printf("Water Added=%d\t",left_height-height[start_ind]);
}
// Get next bar for comparison
start_ind++;
}
else
{
printf("start_ind=%d, end_id=%d\t",start_ind,end_ind);
if (height[end_ind]>right_height)
{
//Update Right taller bar
right_height=height[end_ind];
printf("right_height=%d\t",right_height);
}
else
{
// Caluclate volume
vol=vol+right_height-height[end_ind];
printf("water Added =%d\t",right_height-height[end_ind]);
}
// Get next bar for comparison
end_ind--;
}
printf("\n");
}
return vol;
}
void main()
{
int vol, i,j,k, height[]= {7,5,1,6,5,0,9};
//Diaplay the bar structure for eater trapping
printf("\n\n\t \tTHE WATER TRAPPING PROBLEM \n\n");
for (i=0; i<9;i++)
{
printf("\t\t");
for (j=0; j<=6;j++)
{
if (height[j]-(9-i)<0)
printf(" ");
else
printf("[_]");
}
printf("\n");
}
printf("\t\t");
for (j=0; j<=6;j++)
printf("___");
printf("\n");
printf("Heights of bars:");
for (j=0; j<=6;j++)
printf(" %d ",height[j]);
printf("\n\n For the Above bar Structure \n\n");
//call fucntion to calculate total volume
vol=FindVol(height,7);
printf("\n\nThe total water that will be collected is %d",vol);
}
Solution with Java
import java.util.*;
public class WaterTrap {
public static int FindVol(int height[], int num) {
int vol = 0;
int left_height=0;
int right_height=0;
int start_ind=0;
int end_ind=num-1;
while(start_ind<=end_ind)
{
if (height[start_ind]<height[end_ind])
{
if (height[start_ind]>left_height)
left_height=height[start_ind];
else
vol=vol+left_height-height[start_ind];
start_ind++;
}
else
{
if (height[end_ind]>right_height)
right_height=height[end_ind];
else
vol=vol+right_height-height[end_ind];
end_ind--;
}
}
return vol;
}
public static void main(String args[]) {
int[] height= {5,3,1,2,5,0,4};
System.out.println(FindVol(height,height.length));
}
}Solution with Python
#Function to calculate volume of water that can be trapped
def FindVol( height, num):
#initialise variable
vol = 0
left_height=0
right_height=0
start_ind=0
end_ind=num-1
while(start_ind<end_ind):
# compare heights of left and right bars
if (height[start_ind]<height[end_ind]):
if (height[start_ind]>left_height):
#update new left higher bar
left_height=height[start_ind]
else:
# calculate volume between left bar and current bar
vol=vol+left_height-height[start_ind]
#update left bar index
start_ind=start_ind+1
else:
if (height[end_ind]>right_height):
#update new right higher bar
right_height=height[end_ind];
else:
# calculate volume between right bar and current bar
vol=vol+right_height-height[end_ind]
#update right bar index
end_ind=end_ind-1
return vol
height= []
i=0
#Read the count of bars to be stored
n=int(input("Number of elements you want to add--->"))
while i<n:
height.append(int(input("input value--->")))
i=i+1
print(FindVol(height,n))
Note: We have used arrays that are initialized in the C and Java Code. You can modify to get the array values form user.
Be First to Comment