Beyond awesome | 越而胜己

This problem is a hard yet very popular interview problem. I came across this problem in high school in Sherol's AIVD course, and spent hours to come up with an extremely complex divide-and-conquer solution, which wasn't efficient at all.

The key to solving this problem is not programming techniques, but to observe that the volume of water on index i is the min value of max(height[0..i-1]) and max(height[i+1...n-1]).

After we make this observation, we can come up with a naive solution: for each index i, go out from i to both ends of the array and compute the max values on both sides. This is an $\O(n^2)$ solution. We can optimize it by precomputing the left-max and right-max values for every index, by traversing the array in both directions in $\O(n)$ time. Then we can traverse the array again to compute the amount of water on each index, which is also $\O(n)$.

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)

left_max = [0] * n
left_curr_max = 0
for i in range(n):
left_max[i] = left_curr_max
left_curr_max = max(left_curr_max, height[i])
print(left_max)

right_max = [0] * n
right_curr_max = 0
for i in range(n-1, -1, -1):
right_max[i] = right_curr_max
right_curr_max = max(right_curr_max, height[i])
print(right_max)

water = []
for i in range(n):
min_lr = min(left_max[i], right_max[i])
if min_lr < height[i]:
water.append(0)
else:
water.append(min_lr - height[i])
# water = [min(left_max[i], right_max[i]) for i in range(n)]
print(water)
return sum(water)