Post

Leetcode 42. Trapping Rain Water

Explanation for Leetcode 42 - Trapping Rain Water, and its solution in Python.

Posted
By Hyeonu(Eric) Kim
2 min read

Problem

Leetcode 42 - Trapping Rain Water

Example:

Desktop View

1
2
3
4
5
6

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

Approach

We can use a 2 pointer and keeping track of max height of from left and right to solve this problem.

  • if maxLeft < maxRight
    • increment left pointer
    • update maxLeft
    • add maxLeft - height[left] to res
  • else
    • decrement right pointer
    • update maxRight
    • add maxRight - height[right] to res

Visualization of the Approach:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

height = [0,1,0,2,1,0,1,3,2,1,2,1]
          l                     r
maxLeft = 0
maxRight = 1
res = 0

Since maxLeft < maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
            l                   r
maxLeft = 1
maxRight = 1
res = 0

Since maxLeft >= maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
            l                 r  
maxLeft = 1
maxRight = 2
res = 0

Since maxLeft < maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
              l               r  
maxLeft = 1
maxRight = 2
res += 1-0 = 1

Since maxLeft < maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                l             r  
maxLeft = 2
maxRight = 2
res += 2-2 = 1

Since maxLeft >= maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                l           r  
maxLeft = 2
maxRight = 2
res += 2-1 = 2

Since maxLeft >= maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                l         r   
maxLeft = 2
maxRight = 2
res += 2-2 = 2

Since maxLeft >= maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                l       r   
maxLeft = 2
maxRight = 3
res += 3-3 = 2

Since maxLeft < maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                  l     r   
maxLeft = 2
maxRight = 3
res += 2-1 = 3

Since maxLeft < maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                    l   r   
maxLeft = 2
maxRight = 3
res += 2-0 = 5

Since maxLeft < maxRight
height = [0,1,0,2,1,0,1,3,2,1,2,1]
                      l r   
maxLeft = 2
maxRight = 3
res += 2-1 = 6

Thus return 6

Here is the Python code for the solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        
        res = 0
        left, right = 0, len(height) - 1
        maxLeft, maxRight = height[left], height[right]

        while left < right:
            if maxLeft < maxRight:
                left += 1
                maxLeft = max(maxLeft, height[left])
                res += maxLeft - height[left]
            else:
                right -= 1
                maxRight = max(maxRight, height[right])
                res += maxRight - height[right]
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$

Leetcode, Two Pointers, Hard
Leetcode Python Study Two Pointers Hard
This post is licensed under CC BY 4.0 by the author.