Interview Question
Country: United States
I think the intuition is that you know that 2 peaks will either be the same, the first one will be bigger than the other or the second will be bigger than the first. Keep one variable for peak1, one variable for highestPeakSoFar (hpsf)
We will iterate through the bar graph, starting with peak1 = element 0. If we encounter a peak p that ends up being greater than or equal to peak1, we will calculate the amount of water sumOfWater += (Min(peak1, p) - element). Then, we set p as peak1 and repeat the process from there. If we don't encounter a higher peak, we simply set hpsf as the highest peak we've encountered so far that is smaller than peak1. This is because this smaller peak wouldn't affect the water unless it is the final peak.
Finally, if we can't find anymore high peaks, we do the calculation with hpsf,
sumOfWater += (Min(peak1, hpsf) - element)
We are guaranteed To be done with this in 2n operations, which runs in O(n)
Good point.
Then basically, I'd arrange it in this way instead.
We are looking for local maxima in the array and then compare the distance between them.
for (int i = 0; i <bargraph.length; i++) {
if (bargraph[i-1] < bargraph[i] && bargraph[i] > bargraph[i+1]) {
//check this local max with the previous local max and find the water between them and add
}
}
I think this modification should work
I think the algorithm needs to be:
1: Find the first local maxima, call it "left"
2. Scan the rest of the array for either a maxima >= the left, or the highest in the array. Call it "right". If none, stop.
3. Compute water between left and right.
4. Assign right to left.
5. Goto 2
Unfortunately, this is not O(n) though! it is O(n^2). think about
{5,1,4,1,3,1,2}
This question is a pain!
Also, the maxima detection has to be more sophisticated than in your example. for cases like
{..., 3, 4, 4, 3, ...} and {..., 3, 4, 4, 5, ...}
Yeah this is the algorithm I'm thinking. but it would be O(n) because you check left and right at most twice.
So it would still be O(2n) -> O(n)
Find the bar with max heights and second max heights
Calculate water in between the two as sum of second max minus every bar heights
These two bar divided bars on three parts. Recursively, solve for bars in the left part and in the right, inclusively with dividers.
Note that after 2nd recursion and on, highest will always be on the border, so will have 2 parts, not three, without loss of generality of the recursive step.
Time complexity O(n). Even though search max will go each bar on every recursion, we only do it on just a portion of bars for which water is not counted, which reduces exponentially. Same reasoning as quickselect is O(n)
@Javeed agree this same logic can be well done without recursion. After first recursion, on the left it is always water on the right and step-in to the left and on the right it is always water on the left and step in to the right. So, after initial divide you can just iterate down on the left side and iterate up on the right.
@tjcbs2
max 5, second max 4
left:5. middle 5,4 right 4,1,3,1,2
left and middle 0 water, done.
at 4,1,3,1,2
max 4, second max 3
left:4. middle 4,1,3 right 3,1,2
left is 0 water. both middle and right have two maxes on the side so they themselves have only middle parts. first contains 2, second one, total 3
Am I the only who didn't understand this task? Are those bar vertically or horizontally aligned on the graph? What does "maximum amount of storage" mean?
this can be imagined as if the graph is a cross-section of some hills/mountains with rain falling on it. Where would the water collect vs where would it drain off and flow away? You want to calculate how much water is stored. Draw out a graph on paper and you can get a general idea.
a simple example:
[5,1,1,5]
this would look something like (sorry it's time for ascii art):
x x
x x
x x
x x
x x x x
water would collect in this one, you would have 8 units collected after it is done
Assume 1 unit of water is one unit of height per bar on the table (i.e. the x's in the example)
public static int storedVolumeOfBarChart(int[] in) {
return calculateVolumeBetweenAnyTwoPoints(in, 0, in.length - 1);
}
private static int calculateVolumeBetweenAnyTwoPoints(int[] in, int leftPos, int rightPos) {
// "Trim" the slopes on either side
int leftCrestPos = leftPos, rightCrestPos = rightPos;
while (leftCrestPos < rightCrestPos - 1 && in[leftCrestPos + 1] > in[leftCrestPos])
leftCrestPos++;
while (leftCrestPos < rightCrestPos - 1 && in[rightCrestPos - 1] > in[rightCrestPos])
rightCrestPos--;
if (rightCrestPos - leftCrestPos > 1)
return calculateVolumeBetweenCrests(in, leftCrestPos, rightCrestPos);
else
return 0;
}
private static int calculateVolumeBetweenCrests(int[] in, int leftPos, int rightPos) {
int totalStorage = 0;
if (in[leftPos] < in[rightPos]) {
int currentPos = leftPos + 1;
int waterLevel = in[leftPos];
while (currentPos < rightPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos++;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, currentPos, rightPos);
break;
}
}
} else {
int currentPos = rightPos - 1;
int waterLevel = in[rightPos];
while (currentPos > leftPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos--;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, leftPos, currentPos);
break;
}
}
}
return totalStorage;
}
public static int storedVolumeOfBarChart(int[] in) {
return calculateVolumeBetweenAnyTwoPoints(in, 0, in.length - 1);
}
private static int calculateVolumeBetweenAnyTwoPoints(int[] in, int leftPos, int rightPos) {
// "Trim" the slopes on either side
int leftCrestPos = leftPos, rightCrestPos = rightPos;
while (leftCrestPos < rightCrestPos - 1 && in[leftCrestPos + 1] > in[leftCrestPos])
leftCrestPos++;
while (leftCrestPos < rightCrestPos - 1 && in[rightCrestPos - 1] > in[rightCrestPos])
rightCrestPos--;
if (rightCrestPos - leftCrestPos > 1)
return calculateVolumeBetweenCrests(in, leftCrestPos, rightCrestPos);
else
return 0;
}
private static int calculateVolumeBetweenCrests(int[] in, int leftPos, int rightPos) {
int totalStorage = 0;
if (in[leftPos] < in[rightPos]) {
int currentPos = leftPos + 1;
int waterLevel = in[leftPos];
while (currentPos < rightPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos++;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, currentPos, rightPos);
break;
}
}
} else {
int currentPos = rightPos - 1;
int waterLevel = in[rightPos];
while (currentPos > leftPos) {
if (in[currentPos] <= waterLevel) {
totalStorage += waterLevel - in[currentPos];
currentPos--;
} else {
totalStorage += calculateVolumeBetweenAnyTwoPoints(in, leftPos, currentPos);
break;
}
}
}
return totalStorage;
}
1)start left most
- anonymous March 19, 20152) keep three variables: max= current highest bar, total and current which hold the final total and current temporary units
3) for each bar, adding to the current, until reaching a bar >= max, then add current to total, and reinitialize current
4)Do this until reaching the end of the graph