- Published on
Trapping Rain Water
- Authors
- Name
- Alex Noh
Introduction
Things you should know
1. destructuring
Instead of assigning each value to individual variables separately, there's a method that allows you to do it simultaneously. It's called destructuring. Here's how it works:
enumerate.py
# Instead of this
a = 5
b = 3
# You can do this
a, b = 5, 3
Solutions
1. Two pointers
This approach is quite intuitive and simple. It starts by positioning two pointers at the opposite ends of the array and gradually moving them closer to each other. As they advance, the algorithm calculates the volume of trapped water by comparing the maximum heights encountered on the left and right sides. The time complexity is since it iterates through each element of the array once, making it quite efficient.
main.py
def trapping_rain_water3(heights: List[int]) -> int:
volume = 0
left, right = 0, len(heights) - 1
max_left, max_right = heights[left], heights[right]
while left < right:
max_left, max_right = (max(max_left, heights[left]),
max(max_right, heights[right]))
if max_left <= max_right:
volume += max_left - heights[left]
left += 1
else:
volume += max_right - heights[right]
right -= 1
return volume
2. Stacks
This solution utilizes a stack to keep track of indices as it iterates through the heights array. The time complexity is also .
main.py
from typing import List
def trapping_rain_water(heights: List[int]) -> int:
stack = []
volume = 0
for i, height in enumerate(heights):
while stack and height >= heights[stack[-1]]:
top = stack.pop() # top index
if len(stack) == 0:
break
width = i - stack[-1] - 1
height = min(heights[stack[-1]], heights[i]) - heights[top]
volume += width * height
stack.append(i)
return volume