This is the way I went about the “Largest Puddle on a Bar Chart” problem. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.
Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others efforts.
My Approach
Of course, the most straight-forward approach could be performed by taking each bar, and finding the pool starting at that bar to each of the bars that follow in turn and taking the max. Then move on to the next bar as the starting point and repeat.
This would be a quadratic – O(n^2) – solution, so we’re pretty sure we can do something better.
My approach was to consider the nature of the problem and how the water “flows”. For example, looking at the example graph:
We can see that bars that increase on the left (moving right) will generate no new pool, only bars that decrease from the left. Similarly, bars that decrease from the right (moving left) will end pools, not bars that increase from the right.
Knowing this, we can start a left and right position on each side of the graph and move in. Obviously, they can’t move in sync because there’s no guarantee the pool will have symmetrical beginning and ending points. But we can bring in the left and right sides until we find a pool.
So, we know that water will “flow over” the smaller of two sides. For example, on the graph above, the smaller pool is bounded by the left bar because it’s smaller and additional water will “flow over” it. This means that we only need to keep going until we find a bar bigger than it.
How does all of this flow into the solution? Simply put, we will start a left position at 0 and a right position at bars.Length – 1 and move whichever bar is shorter towards the bar that is taller. As long as we find something smaller than the shorter bar, we accumulate area. The moment we find something larger or equal to the shorter bar, we close off the area, compare to our max area, and begin the cycle again with that new bar being the new left (or right, depending on which we chose) bar.
We can stop the moment left and right cross and the end result should be the max puddle area of the whole chart. This solution is linear – O(n) – in time and constant in space requirements, which is fairly optimal.
My Code
Here is the code for my solution.
public static int FindLargestPuddle(int[] bars)
{
int maxArea = 0;
int leftSide = 0;
int rightSide = bars.Length - 1;
// keep going till we cross
while (leftSide < rightSide)
{
// move from smallest to largest
int currentArea = 0;
if (bars[leftSide] < bars[rightSide])
{
int puddleStart = leftSide;
// go until we find equal bar or cross right side
while (bars[puddleStart] > bars[++leftSide] && leftSide < rightSide)
{
currentArea += bars[puddleStart] - bars[leftSide];
}
}
else
{
int puddleStart = rightSide;
// go until we find equal bar or cross left side
while (bars[puddleStart] > bars[--rightSide] && leftSide < rightSide)
{
currentArea += bars[puddleStart] - bars[rightSide];
}
}
// if puddle is > max, it's the new max
if (currentArea > maxArea)
{
maxArea = currentArea;
}
}
return maxArea;
}
Summary
Hope you had fun with this one! Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.
Have a solution that worked for you but was totally different? I’d love to hear about it!
Stay tuned next week for the next Little Puzzler.