I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.
This is perhaps one of the more fun problems I’ve had to solve in an evaluation situation before. I’m not claiming I have the optimal answer, so I’ll be curious to see what you all come up with as well!
The Problem:
Given an array of int that represents the height of bars in a bar chart, calculate the size of the largest puddle that would form if water were poured over the top of the graph.
You may assume the following:
- All bars have a width of 1
- There is no extra space between adjacent bars.
- There are no negative bars
- The edges of the bar chart are an implicit “zero” height.
Example:
Assume you had the following array:
var bars = new [] { 10, 20, 80, 70, 60, 90, 40, 30, 40, 70 };
We would have the following bar chart with the indicated puddles forming on top:
Note that no water pools on the left side because there isn’t a left “wall” to hold it in.
So in this example, two pools would form: one from the 80-90 bars that hold 30 units of water, and one from the 90 bar to the 70 bar that holds 100 units of water. Thus the largest pool size would have an area of 100.
Spoiler Alert!
Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below.