Initial Solution
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
l = 0
r = n-1
res = 0
step = 0
prevStep = 0
while l < r:
if height[l] <= prevStep:
l += 1
continue
if height[r] <= prevStep:
r -= 1
continue
h = min(height[l], height[r])
w = r - l
for i in range(l+1, r):
if h > height[i]:
step = h - height[i]
res += step
height[i] = h
prevStep = h
return res
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n²) - The outer while loop runs O(n) times, and for each iteration, the inner for loop can traverse up to O(n) elements, resulting in quadratic time complexity.
Space Complexity: O(1) - Only a constant amount of extra space is used for variables (l, r, res, step, prevStep), excluding the input array.
Other Better Solutions
Two Pointer Approach (Optimal)
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
l, r = 0, len(height) - 1
leftMax, rightMax = height[l], height[r]
res = 0
while l < r:
if leftMax < rightMax:
l += 1
leftMax = max(leftMax, height[l])
res += leftMax - height[l]
else:
r -= 1
rightMax = max(rightMax, height[r])
res += rightMax - height[r]
return res
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n) - Single pass through the array with two pointers moving towards each other.
Space Complexity: O(1) - Only constant extra space used for pointers and variables.
Key Insights
This approach eliminates the nested loop by maintaining left and right maximum heights. At each step, we process the side with the smaller maximum, ensuring we can correctly calculate trapped water without scanning the entire array repeatedly.