sanrag83
BAN USER
Comments (2)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
Here is a solution which I believe should be more readable
Credits to Tristan (Tristan's collection of Interview Question) for his approach
int FillWater(int* histogram, int length)
{
int waterCollected = 0;
int *maxLeft = new int [length];
int *maxRight = new int [length];
//For each values, calculate the maximum value to its left
maxLeft[0] = 0;
for(int i = 1; i < length; i++)
{
maxLeft[i] = max(histogram[i1], maxLeft[i1]);
}
//For each values, calculate the maximum value to its right
maxRight[length1] = 0;
for(int i = length  2; i >= 0; i)
{
maxRight[i] = max(histogram[i+1], maxRight[i+1]);
}
//At each index, water collected will be collected, if it is a dip
//Amount of water collected will be [min(maxLeft[i], maxRight[i])  value at that index]
for(int i = 0; i < length; i++)
{
if(maxLeft[i] > histogram[i] && maxRight[i] > histogram[i])
{
waterCollected += (min(maxLeft[i], maxRight[i])  histogram[i]);
}
}
delete[] maxLeft;
delete[] maxRight;
return waterCollected;
}

sanrag83
March 03, 2014 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
This is also a neat solution.. the tricky part being the condition
which ensures that if the histogram is decresing order (either in its entirity or portion of it) then that section is skipped while calculating the trapped water.
 sanrag83 March 04, 2014