Trapping Rain Water

This is a post in a series of posts regarding my solutions to problems on leetcode. Consider this a braindump for my thought process as I solved a problem. In this post, I solved Trapping Rain Water.

A water trap is two columns with at least 1 empty block between them. An empty block is a cell in a column whose height is below the maximum height of the trap. So, given columns:

[1, 0, 1]

column[1] ’s height is less than the maximum height of 1. Therefore, a block at column[1] is an empty block.

Let’s look at another example:

[1, 0, 2]

Maximum height in this case is 1. Maximum height is the lesser between the heights of the two bordering columns in a trap. The water will just spill over the lesser height if we use the greater one as the maximum.

Let’s look at an example with several levels:

[4, 1, 1, 5]

We’re trying to compute for every cell in the trap, so that means having to iterate through every “level” (y-axis) in the trap. That means iterating through every cell above 1 on both the second and third elements, up to the maximum height of 4.

Finally:

[4, 1, 1, 5, 1]

In this example, we do not consider cells from the last element, because it is not inside a trap. That is, the empty cells are not between two bordering columns with a maximum height greater than their respective columns.

My first attempt boiled down to:

1. For each permutation of a trap, count the number of water blocks per layer

However, we’d end up recounting blocks inadvertently. We’d end up with potentially twice as many water blocks as are actually there, as a result.

A possible solution to this is to cache results to subproblems. Hence, my next attempt:

1. Maintain left and right pointers.
2. Count the number of blocks between them, if any (do not increment counter if already visited).
3. Climb up to the next level if possible.
4. Count empty blocks in this level using the same logic in steps 2 and 3.
5. Repeat steps 2, 3, and 4 for every level, and for every position in the `height` array. We move either the left or the right pointer, depending on which one points to a smaller column.

This worked in general, but it timed out for one of the test cases.

To optimize my approach, I decided to just iterate through the levels at the outset. I’d grab the highest height in the array, and iterate through every level from 0 to maxHeight. In each iteration, I’d count all the empty cells inside a “trap” in the level:

1. Find the max height in the array.
2. Iterate through 0 to maxHeight
2.1. Iterate through cells at level i
2.1.1. If we encounter a block, we are now inside a trap; we can now start counting empty cells towards are total count

There’s one last issue: we are not necessarily “inside” a trap just because we see a non-empty block. We also have to find the first non-empty block from the right. This block will representing our trap’s border column at the right.

The pseudo-code for my optimized solution is thus:

1. Find maxHeight in the list
2. Iterate through every level until maxHeight
2.1. Find first non-empty block from the left
2.2. Find first non-empty block from the right
2.3. Count all empty blocks between these two bordering blocks
3. Return total count across all levels.

And I implemented this as follows:

func isEmptyCell(height []int, pos, level int) bool {
    return height[pos] < level + 1
}

func solution(height []int) int {
    n := len(height)
    maxHeight := height[0]
    for _, h := range height[1:] {
        if h > maxHeight {
            maxHeight = h
        }
    }

    var count int
    for i := 0; i < maxHeight; i++ {
        var left int
        right := n - 1
        for left < right {
            if !isEmptyCell(height, left, i) {
                break
            }

            left++
        }

        for left < right {
            if !isEmptyCell(height, right, i) {
                break
            }

            right--
        }

        for left + 1 < right {
            if isEmptyCell(height, left + 1, i) {
                count++
            }

            left++
        }
    }

    return count
}

func trap(height []int) int {
    return solution(height)
}