9 Nov 21

Water trapped within walls

 

Kanda River, Chiyoda City, Tokyo

Here is a variation of a classic coding problem that involves solving how much water can be trapped within walls of varying heights

You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.

Compute how many units of water remain trapped on the map in O(N) time and O(1) space.

For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.

Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.

Understanding the problem

The original problems lists two examples each containing a list of numbers. Each number represents the height of a wall that can trap water. Water can only be contained between two walls, as illustrated in the diagram below


Solving it the wrong way

The problems explicitly state that it needs to be solved in O(n) runtime and O(1) memory. By traversing from both ends towards center you could determine the amount of water contained within the walls. Both examples listed in the original problem allow the following solution.

In the solution above, I keep track of the shortest  wall at the two ends and establish that wall as the minimum height of the entire "container" of water. Any water over this should not be contained, or so I thought.

While it works for the given examples, it fails for examples where elevation changes can trap more water, like the example illustrated in the diagram below -

Improved Solution ?

O(N) doesn't necessarily mean a single pass. It could be cN, where c is some constant. The run time can increase linearly, but shouldn't increase exponentially.

Another approach involved the following steps -

  • With the first pass of the list determine the max height of the wall
    • With the max height we can determine how far the water can rise.
  • In the second pass keep track of the height of the wall and only change it if it increases.

The fallacy of this solution is that it does not address what happens if the elevation decreases

Solution

One way of thinking about this problem, is exactly as it is described - an elevation map. The wall with the lowest elevation will trap water at least up to that height. I got that right in my original approach. What I got wrong was traversing the list from both ends simultaneously.

We keep track of the "retaining" walls on either end of the list - left and right. We only advance from the lowest of the two retaining walls.


Each advance -

  • Allows us to calculate the amount of water trapped against the retaining wall we are advancing from
  • Each advance also presents us with the opportunity to increase the height of the retaining wall that we are advancing from.

Since we only advance from the lowest of either retaining walls, the direction of our advance can change.

Original source code and discussion from Leetcode here. 

class Solution {
public:
    int trap(int A[], int n) {
        int left=0; int right=n-1;
        int res=0;
        int maxleft=0, maxright=0;
        while(left<=right){
            if(A[left]<=A[right]){
                if(A[left]>=maxleft) maxleft=A[left];
                else res+=maxleft-A[left];
                left++;
            }
            else{
                if(A[right]>=maxright) maxright= A[right];
                else res+=maxright-A[right];
                right--;
            }
        }
        return res;
    }
};

References

https://leetcode.com/problems/trapping-rain-water/discuss/17357/Sharing-my-simple-c%2B%2B-code%3A-O(n)-time-O(1)-space


show some love