James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

Image Galleries

.NET

CSharp

Little Wonders

Little Wonders

vNext

Solution to Little Puzzlers–Largest Puddle on a Bar Chart

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:

GraphPool

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.

Print | posted on Monday, April 13, 2015 8:56 PM | Filed Under [ My Blog C# Software .NET Little Puzzlers ]

Powered by: