08/02/2018

[Java] Calculate maximum capacity of 2D shaped object

This problem looked harder than it actually is:

Imagine an island that is in the shape of a bar graph. When it rains, certain areas of the island fill up with rainwater to form lakes. Any excess rainwater the island cannot hold in lakes will run off the island to the west or east and drain into the ocean.

Given an array of positive integers representing 2-D bar heights, design an algorithm (or write a function) that can compute the total volume (capacity) of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1.

Example: Given [1,3,2,4,1,3,1,4,5,2,2,1,4,2,2], return 15 (3 bodies of water with volumes of 1,7,7 yields total volume of 15)



We can find the solution in O(N) time and O(N) space as such by first walking from one side of the island to the other and tracking the current maximum elevation we find, starting from elevation 0.
Each section of the island can hold exactly curr_max - section_elevation water, we track this in a secondary array.

At the end of the first pass we have all the correct values for the sections starting from one end of the island to the highest peak. We still need to perform another pass though, since we might still be missing the correct values for the section of the island starting from the opposite side until the highest peak.

We therefore loop again, this time in the opposite direction, and apply the same logic but also add a check to break the loop as soon as we reach a peak as high as the highest we found.

Now our auxiliary array will contain the capacity for each section of the island, we simply need to scan that and sum up all values to get our answer.

You can check my implementation of getIslandLakesCapacity on my Gist alongside some test cases in IslandLakesCapacityJTests.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.