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.
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.
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)
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 = height 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 = height 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 and error occurs.
But rest asure, for loop will not be entered at all if the condition is not met.
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 = height. So we proceed to i = 4.
When i = 4, height > height. So we can fill water between column 4 and column 0. The water to be filled is (4 – 0 – 1) * min(height, height) = 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).