Resource Library

You’re invited to check out out all the different learning resources in the guide: problems and projects, former Google interview questions, online courses, education sites, videos, and more. You can search for your favorite topics.

Your mission: Apply all the coding knowledge you've gained to write a program that solves a fascinating problem. Given an array of integers representing varying terrain heights, you need to find the volume of the lakes that form when it rains. Good luck! (Note: The example code solution snippets are on LeetCode.com, which may require login to access)

Take the challenge

Google

The Challenge

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)

An image showing the volume of water
Learning objectives

This question offers practice with algorithms, data structures, Big-O, defining functions, generalization, efficiency, time and space complexity, and anticipating edge cases.

Solution explained, commentary

Using the Dijkstra algorithm, which finds the shortest paths between nodes in a graph

Consider a function f(x) which for a node x tells you what the water level is for that node (if you subtract the height h(x) at that point and integrate over the whole are then you have the answer)

Now f(x) = min_{path p from x to answer sinkhole} max_{q in p} h(q)

So this is a version of the Dijkstra algorithm using the edge weight max instead of the usual sum.

O(N) Solution: Scan left to right, then right to left

Overall strategy: We make use of the fact that every graph consists of an uphill section, and a downhill section. A single pass will only work on an "uphill" section of the graph. So we solve the left uphill portion with a left to right scan, and then reverse direction to solve the right downhill section with a right to left pass, thus turning the downhill section into an uphill section.

First pass: Scan left to right keeping track of maximum possible water level. Each time a bar greater than or equal to the height of the water level is found, accumulate the lake so far, and update the water level. If no such bar >= the waterlevel is found, do not accumulate the lake. The final bar will always constitute such a condition. The first pass finds the volume of the lakes to the left of the rightmost bar of max height. Record the position of the final max height bar (to the right of which there exists no bar of greater or equal height).

Second pass: We now iterate from right to left (keep the running total from before). We already know the total volume of the lakes identified in the first pass. On the second pass, we find the volume of the remaining lakes.

The second pass terminates when we reach the final max height bar from the 1st pass. Take care to accumulate the final lake.

This approach breaks the tracking of “interesting” columns into a separate step. Doing that costs more time, but might well make for more-readable code.

Walk in from the left edge and the right edge simultaneously.

This approach relies on always knowing that the leftmost (rightmost) edge we’re looking at *must* be on the low side of any basin. Then alternatively work either the left side or the right side towards the middle depending on which one is lower, so as to preserve that invariant.

When left meets or crosses right, we’re done.

Testing suggestions

  • As with solving any coding problem, get in the habit of running tests on your code, to both find bugs and optimize
  • Possible base case tests: lakes shaped like bowls v. buckets, lakes with uneven sides, ranges at the end(s) that hold no water
  • Possible pathological case tests: terrain that only increases or decreases (i.e. slopes with no lakes), uniformly level terrain, 1 or 2 bars total
  • Code snippet for solution

    See the suggested solutions for the version of the problem posted on LeetCode, at

    https://leetcode.com/problems/trapping-rain-water/solution/

    (login may be required). We recommend especially considering the dynamic programming solution (#2)