Brute Force solution: TLE
class Solution:
def trap(self, height: List[int]) -> int:
# time O(N^2) space O(1)
if not height:return 0
size = len(height)
water =0
for i in range(1,size-1):
l_max = r_max = 0 # each time check l,r max at pos i, need to reset
# l_max
for j in range(i,-1,-1):
l_max = max(l_max,height[j])
# r_max
for k in range(i,size):
r_max=max(r_max,height[k])
water += min(l_max,r_max) - height[i]
# water at pos i
return water
Solution 2: memo
class Solution:
def trap(self, height: List[int]) -> int:
# time O(N) space O(N)
if not height:return 0
size = len(height)
water =0
# cache l_max and r_max at each position i
l_max=[0]*size
r_max=[0]*size
# initialize l, r height
l_max[0] = height[0]
r_max[size-1] = height[size-1]
# l--->r , cache l_max at pos i, round 1
for i in range(1,size):
l_max[i] = max(l_max[i-1],height[i])
# r --->l,cache r_max at pos i, round 2
for j in range(size-2,-1,-1):
r_max[j] = max(r_max[j+1],height[j])
# sum up historical min_maxl/r at pos i, round 3
for k in range(size):
water += min(l_max[k],r_max[k]) - height[k]
# water at pos i
return water
Solution 3: Two Pointers
class Solution:
def trap(self, height: List[int]) -> int:
"""
main idea: two pointers. l, r move toward each other. get current l_max and r_max;
then based on case, 1: l_max < r_max 2: r_max < l_max to get water at pos left/ right
"""
# time O(N) space O(1)
if not height:return 0
size = len(height)
water =0
l, r = 0, size -1
# initialize l,r max height
l_max, r_max = height[0],height[size-1]
while l<=r:
l_max = max(height[l],l_max)
r_max = max(height[r],r_max)
if l_max < r_max:
water += l_max - height[l]
l += 1
else:
water += r_max - height[r]
r -=1
return water