Qualcomm Interview Question
Software Engineer / DevelopersInterview Type: In-Person
The first solution takes O(n) space as well as O(n) time. By doubling the time (the time complexity will still be O(n)), we can also find out the volume.
For the sake of simplicity, let us assume that the area of cross-section of each histogram is 1 square unit. Then, the volume of water = Total height of water above all the towers cubic units. The height of water above any given tower is determined by the following formula:
heightOfWater[i] = max(min(LeftMax[i],RightMax[i]) - height[i], 0).
Now, we can look at it as follows. Move from left to right. Start from the left most maximum (the first tower), and move right. All the towers that have lesser height than that will have some amount of water above it, provided there is another tower of height >= it. Consider two towers this way, i and j, such that i < j, and height[i] < height[j] and for all k < j and k > i, height [k] < height[j]. Then, the height of water above each tower is calculated using the formula:
heightOfWater[k] = height[i] - height[k].
totalHeightOfWater += height[i] - height[k].
Then set i = j and find the next j. If there is no j, then stop.
Now, start moving from the right to the left and do the same, with i > j, and height[i] < height[j] and for all k < i and k > j, height [k] < height[j]. Then, the height of water above each tower is calculated using the formula:
heightOfWater[k] = height[i] - height[k].
totalHeightOfWater += height[i] - height[k].
Then set i = j and find the next j. If there is no j, then stop.
We can calculate the total height of water, while we are calculating individual heights.
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[i-1], maxLeft[i-1]);
}
//For each values, calculate the maximum value to its right
maxRight[length-1] = 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;
}
Time complexity: O(N)
int findTrappedWater(int* H,int size)
{
int i,j,water=0,temp;
for(i=0;i<size;)
{
j=i+1;
temp=0;
while(j<size && H[i]>H[j])
{
temp+=H[j];
j++;
}
if(j!=size) // decreasing length histogram
water+=(j-i-1)*H[i]-temp;
i=j;
}
return water;
}
Complete code here: ideone.com/xCsHn
@shondik
i think you are missing the case when going from left to right you don't find any H[j] > H[i]. But even in that case we might have water getting collected and the way to do it completely would be to traverse the array once more from right to left using the same logic.
This is also a neat solution.. the tricky part being the condition
if(j!=size) // decreasing length histogram
water+=(j-i-1)*H[i]-temp;
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.
On similar lines, this should work
/* Set previous and next values for all buildings */
void SetPrevNext()
{
int i, max_height = -1;
prev[0] = -1;
next[n-1] = -1;
/* Set previous values */
for (i=1;i<n;i++)
{
if(h[i-1]>h[i]) /* If height of prvious building is more */
{
prev[i] = i-1;
}
else if(h[i]<h[prev[i-1]]) /*Check previous height */
{
prev[i]=prev[i-1];
}
else if(max_height > -1 && h[i]<h[max_height]) /* Local Maximum height */
{
prev[i] = max_height;
}
else /* heighest tower */
{
prev[i] = -1;
max_height = i;
}
}
/* Set next heights */
max_height = -1;
for (i=n-2;i>=0;i--)
{
if(h[i+1]>h[i]) /* height of next tower is more */
{
next[i] = i+1;
}
else if(h[i]<h[next[i+1]])
{
next[i]= next[i+1];
}
else if(max_height > -1 && h[i]<h[max_height]) /* local maximum tower height */
{
next[i] = max_height;
}
else /* heighes tower */
{
next[i] = -1;
max_height = i;
}
}
}
int FillWater()
{
int i, total_water = 0;
int height, width;
for (i=1;i<n-1;i++)
{
if(prev[i]>0 && next[i]>0)
{
/*height of water based on smaller next or previous tower */
height = (h[prev[i]]<h[next[i]])?(h[prev[i]]-h[i]):(h[next[i]]-h[i]);
/* Width spanning the previos and next towers */
width = (next[i]-prev[i]-1)*W;
//printf("\nHeight : %d, Width : %d for %d",height, width, h[i]);
total_water += (height * width);
}
}
return total_water;
}
/**
* find water captured between towers
* works perfactly and complexity is O(n)
*/
long int getWaterStorage(std::vector<long int> const & towers) {
if(towers.size() < 3) return 0;
int i = 1;
long int water= 0;
while(i<towers.size()) {
//first find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int s = i-1;
//second find last element in discending order
while(i<towers.size() && towers[i-1]>=towers[i]) ++i;
int m = i -1;
if(s == m) break;
//third find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int e = i -1;
if(m == e) break;
water += std::min(towers[s], towers[e]) - towers[m];
}
return water;
}
int main() {
std::vector<long int> v;
int n;
//read size of v
std::cin>>n;
//read v array
for(int i =0;i<n;++i)
{
long int e;
std::cin>>e;
v.push_back(e);
}
std::cout<<getWaterStorage(v)<<std::endl;
return 0;
}
areeb$ ./a.out
3 << this is size of the array
2 1 3 << these are element separated by space
1 << output
areeb$ ./a.out
3
1 2 3
0
areeb$ ./a.out
3
3 2 1
0
areeb$ ./a.out
3
3 1 2
1
/**
* find water captured between towers
* works perfactly and complexity is O(n)
*/
long int getWaterStorage(std::vector<long int> const & towers) {
if(towers.size() < 3) return 0;
int i = 1;
long int water= 0;
while(i<towers.size()) {
//first find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int s = i-1;
//second find last element in discending order
while(i<towers.size() && towers[i-1]>=towers[i]) ++i;
int m = i -1;
if(s == m) break;
//third find last element in ascending order
while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
int e = i -1;
if(m == e) break;
water += std::min(towers[s], towers[e]) - towers[m];
}
return water;
}
int main() {
std::vector<long int> v;
int n;
//read size of v
std::cin>>n;
//read v array
for(int i =0;i<n;++i)
{
long int e;
std::cin>>e;
v.push_back(e);
}
std::cout<<getWaterStorage(v)<<std::endl;
return 0;
}
areeb$ ./a.out
3 << this is number of elements in the array
2 1 3 << array, all element on one line space sparated
1 << output
areeb$ ./a.out
3
1 2 3
0
areeb@$ ./a.out
3
3 2 1
0
areeb$ ./a.out
3
3 1 2
1
# O(n) time, O(1) space
def area(heights):
ret = 0
cur_valley_area = 0
max_so_far = 0
index_of_max_so_far = -1
for i, h in enumerate(heights):
if h < max_so_far:
cur_valley_area += max_so_far - h
else:
ret += cur_valley_area
max_so_far = h
index_of_max_so_far = i
cur_valley_area = 0
# add everything that comes after (to the right of) the max height in the array
max_right_so_far = 0
for i in xrange(len(heights) - 1, index_of_max_so_far, -1):
h = heights[i]
max_right_so_far = max(h, max_right_so_far)
ret += max_right_so_far - h
return ret
# O(n) time, O(1) space
def area(heights):
ret = 0
cur_valley_area = 0
max_so_far = 0
index_of_max_so_far = -1
for i, h in enumerate(heights):
if h < max_so_far:
cur_valley_area += max_so_far - h
else:
ret += cur_valley_area
max_so_far = h
index_of_max_so_far = i
cur_valley_area = 0
# add everything that comes after (to the right of) the max height in the array
max_right_so_far = 0
for i in xrange(len(heights) - 1, index_of_max_so_far, -1):
h = heights[i]
max_right_so_far = max(h, max_right_so_far)
ret += max_right_so_far - h
return ret
A solution with linear time (2 passes), constant space.
Loop to find the local maxima (aka towers). A local maximum is bigger than the element before and the element after, or it is an edge element (first / last) and bigger than the one after / before respectively. Take into account maximum with more than one column (columns are equal). Store the maxima locations in a pair vector (if single column maximum, both values of the pair are equal).
If you have less than 2 maxima, return 0 - no water kept.
Loop on the maxima locations, two at a time (looking at the valley between). The water kept between two maxima is the difference between the histogram value and the smaller of the two maxima values, floored by 0.
A discrete graph can be partitioned into alternating increasing and decreasing runs optionally interspersed with optional runs. Define a valley as a decreasing run followed by an optional number of constant runs followed by an increasing run. The height of the valley is the minimum of its leftmost point (the highest point on the decreasing run) and its rightmost point (the highest point on the increasing run). Its length is the total number of elements in its constituent runs. A valley's basin is its height times its length, which is the amount of water that valley can contain. Draw a picture to see why this makes sense.
Translating this idea into an algorithm is easy. You just traverse the histogram left to right, keeping track of decreasing, constant and increasing runs as you go. If you set it up correctly, you won't need to handle leftmost and rightmost "half-valleys" as special cases; they will just be valleys where the height is zero because one of the two end points has height zero.
Sorry, my description of calculating the basin area left something out. You also need to calculate the sum of the heights of each of the points in the valley. You then subtract that from the product of the length and min height I already described.
No need to overcomplicate with increasing and decreasing runs. Simply consider the list of elements which are greater than all elements to its left. Then define anything in between a consecutive pair of such elements as a valley. The water in such a valley is just sum (height of left end of valley - height of bar). Now just handle all the things to the right of the greatest height specially.
For each index, calculate what the tallest point in the histogram preceding that index is. This is easy and O(n) because max_before[n] = max (max_before[n-1], histogram[n]). Now, also for each index, calculate a similar max_after array (calculate from the back using max_after[n] = max (histogram[n], max_after[n+1])). Now, for each index n, water_height[n] = min (max_before[n], max_after[n]). At this point, loop over the indices i = 0...n-2 and do:
Edit: This calculation is for the case when the histogram is represented as a line graph, not a bar graph. In the case of a bar graph, you can use the same technique and the logic will be very similar (the formula will actually be simpler).
- eugene.yarovoi February 16, 2012The algorithm is linear time overall.