The Stone Wall Codility challenge proved more difficult for me than the rating it is attributed (easy). I still think it’s at least a medium level challenge, at least for the O(N) complexity I was aiming for.
The problem consists of finding the solution to the minimum necessary number of blocks needed to build a skyline of a city. Each building’s height is given in an array and we must find the minimum number of rectangular stone blocks which can be used to fill that skyline.
The trick is to realize that whenever there is a peak, it’s best to consider the stone block which is added for that peak to be as tall as the difference between its height and it’s tallest neighbour’s height.
At the same time, if two or more consecutive elements of the skyline have the same height, they are considered to be the same edge (can be made with the same stone block).
We combine these two conditions and keep a stack where we place the horizontal edges. They will be placed in an ascending order and after we go over on peak, we eliminate one edge, and add the block which was used to create that edge to the sum of all blocks.
Here is the report.
Do you think there is a better solution? Or maybe you need more information about this one? Share in the comments below!