LC 42, Trapping rain water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Initial thoughts

Horizontal

We can think of each column as a container for water and how much it can have is determined by the min of the max left and max right.

Vertical

BF

The water accumulate above each column is determined by the min of the left max and right max.

        total_h = 0
        for i in range(len(height)):
            max_right = max_left = height[i]
            for j in range(i, -1, -1):
                max_left = max(max_left, height[j])
            for j in range(i, len(height)):
                max_right = max(max_right, height[j])

            total_h +=  (min(max_right, max_left) - height[i])

        return total_h

It runs in O(n^2)

DP

In Brute Force, we repeatedly find the left and right max of a given point. What if we store it? Allocate an array to keep track of the max left height at position i. Iterate from left to right. max_left[0] = height[0] is the base case. max_left[i] = max(max_left[i – 1], height[i]). Do the same for max left, except this time, the base case starts from the right. max_right[len(height) – 1] = height[-1]. and max_right[i] = max(max_right[i + 1], height[i]).

We have computed the max_left and max_right at i for each i in O(n) time.

        if not height:
            return 0
        max_left = [-1] * len(height)
        max_right = [-1] * len(height)
        max_left[0] = height[0]
        max_right[len(height) - 1] = height[-1]
        for i in range(1, len(max_left)):
            max_left[i] = max(max_left[i - 1], height[i])

        for i in range(len(height) - 2, -1, -1):
            max_right[i] = max(max_right[i + 1], height[i])
        total_h = 0
        for i in range(len(height)):
            total_h += min(max_right[i], max_left[i]) - height[i]

        return total_h

Bugs: Forget edge case of empty input

At first, I didn’t have

if not height: return 0

so when the input is empty, the code will try to access height[0] and error occurs.

But rest asure, for loop will not be entered at all if the condition is not met.

stack

We notice that we can only accumulate water if there are higher columns on both sides.

If we iterate through the height list and keep track of the columns that could accumulate water because of higher left side. The index of the column will be pushed on the stack if it is smaller than top of the stack.

Then once we see a right column that’s higher than top of the stack, we know we can fill water in it since the columns on the stack are there because they are smaller than some previous column. We fill till top of the stack is larger or equal to the current column.

This algorithm will “smooth out” smaller pond so the bigger columns on two side can assume the space between them is “flat”.
An example will help.

0   0          0   0 
00 00          00000 
00000    ->    00000 
00000          00000 
00000          00000 

at i = 3, stack = [0,1,2]
We then see a column with height 4. It is larger than 3 so we know we can at least fill water to column 2 to bring its height to min(second top of stack, 4). In this case. We fill column 1 with on water and smooth out the “hole” on top of column 2.
We record how much water we fill; we just filled 1 unit of water.

We then will proceed to fill the hole between column 0 and column 4.
The stack now is [0,1]. We i = 3 3. since height[3] = height[1]. So we proceed to i = 4.
When i = 4, height[4] > height[1]. So we can fill water between column 4 and column 0. The water to be filled is (4 – 0 – 1) * min(height[4], height[0]) = 3.

So the total water filled is 4.

        stack = []
        res = 0
        curr = 0
        for curr in range(len(height)):
            while(stack and height[stack[-1]] < height[curr]):
                top = stack[-1]
                stack.pop()
                if not stack:
                    break
                filled_dist = curr - stack[-1] - 1
                filled_height = min(height[stack[-1]], height[curr]) - height[top]
                res += filled_dist * filled_height

            stack.append(curr)


        return res

We append when the stack is empty or when the current column could potentially hold water with top of stack( smaller than top of stack).

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax