Python Algorithm Q8
Q8 trapping-rain-water
Q
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Sample Input
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
In this case, 6 units of rain water (blue section) are being trapped.
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
1. My Solution <- Given Solution #1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def trap(self, height: List[int]) -> int:
if not height: #check if the list is empty or not
return 0
volume = 0
left, right = 0, len(height) - 1 #each first & last idx
left_max, right_max = height[left], height[right] #initial value is both edge(right & left).
while left < right: #while two-pointer meets
left_max, right_max = max(heigt[left], left_max),
max(heigt[right], right_max) #compare previous value against current value
if left_max <= right_max: #until both right & left max column converges to the highest column
volume+= left_max - height[left]
left+=1
else:
volume+= right_max - height[right]
right-=1
return volume
#for testing
a = Solution()
s = [0,1,0,2,1,0,1,3,2,1,2,1]
print(a.trap(s))
[By using two pointer]
Volume is the answer(=total amout of water). Assign fisrt and last idx to left & right. And initiate max value with the value of the both sides.
Do loop while left meets right. Keep comparing which is the max then update the left & right max.
The side that met the highest column first became the standard and the other side converges to the standard. When right max is bigger, left pointer idx ++ & calculate the amount of water(by left max - current height). Vice versa.
Let’s take an example, when left(idx==0) is the highest value. Then left_max is the highest, so only “else” event occurs. Left pointer is fixed and only right pointer moves downward. Vice versa(when right==highest).
The other case is when the highest column is located in the center. Left and right converges to the center alternately, and fixed when they meet the highest one.
2. Given Solution #2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def trap(self, height: List[int]) -> int:
stack = [] #stack = index
volume = 0
#when meet the inflection point(변곡점), the point when the current height is higher than the previous one.
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
# 1. stack is not empty 2. height[now] > height[prev]
#pull out from the stack
top = stack.pop()
if not len(stack): #when len = 0
break
distance = i - stack[-1] - 1
waters = min(height[i], height[stack[-1]]) - height[top]
volume += distance * waters
stack.append(i)
return volume
[Using Stack]
From concept, it is so complicated solution. Even I can’t understand it until now. The point is that calculate value at the inflection point. “height[i] > height[stack[-1]]” means that until it meets the condition, height consistently decreased. So pop value from the stack(=idx) and multiply the distance and height gap. That is the water to be added.
(**0에서 출발해 매번 스택에 값을 넣으면서 변곡점이 있는지 체크한다. 그리고 변곡점이 발생한 지점이 감지되면 이전까지 높이가 계속 낮아지거나 같았음을 의미하므로 스택에서 하나씩 꺼내 높이 차이와 거리를 곱해 물의 양을 계산한다.)
Solving this problem with the stack is above my capability. Some day, I’ll review it again.
Overall Review
Really really tough problem for me. Solution with the two-pointer is understandable(Likewise complicated but better than stack…). But using stack is never ever make sense and completely out of my capacity. Only studying more and more makes me handle complicated algorithm like those…. Good luck to myself…!