Resource Library

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)

Learning objectives

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

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

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)

def trap(self, height):    left_index, right_index = 0, len(height) - 1    left_max, right_max = 0, 0    output = 0    while left_index < right_index:        if height[left_index] <= height[right_index]:            left_max = max(left_max, height[left_index])            output += max(0, left_max - height[left_index])            left_index += 1        else:            right_max = max(right_max, height[right_index])            output += max(0, right_max - height[right_index])            right_index -= 1    return output    

public int trap(int[] height) {  int trappedWater = 0;  int leftIndex = 0;  int rightIndex = height.length - 1;  int leftMax = 0;  int rightMax = 0;  while(leftIndex < rightIndex) {    if (height[leftIndex] <= height[rightIndex]) {      leftMax = Math.max(leftMax, height[leftIndex]);      trappedWater += Math.max(0, leftMax - height[leftIndex]);      leftIndex += 1;    }    else {      rightMax = Math.max(rightMax, height[rightIndex]);      trappedWater += Math.max(0, rightMax - height[rightIndex]);      rightIndex -= 1;    }  }  return trappedWater;}