Water Trapping Problem Solution

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

Water Trapping Initial

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

water trapping 3

In the second iteration LEFT=2,  RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-1)=6

Solution image 4

In the third  iteration LEFT=3,  RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-6)=1

solution image 5

In the fourth iteration LEFT=4, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-5)=2

Water Trapping image 5

In the fifth iteration LEFT=5, RIGHT=6 and the volume of water added is LEFT_HEIGHT – HEIGHT[LEFT] (7-0)=7

Image 6

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);
}
C code Output

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

Leave a Reply

Your email address will not be published. Required fields are marked *