### View *Trapping Rain Water* on LeetCode

## Statistics

**Time Complexity**

O(n) - The program iterates through each element in the input list, resulting in the O(n) time complexity.

**Space Complexity**

O(1) - The number of variables created is independent of the input list, resulting in the O(1) space complexity.

**Runtime Beats**

69.18% of other submissions

**Memory Beats**

61.67% of other sumbissions

## Explanation

Before searching the list, initialize all the variables: `trapped_water`

to 0, `l`

and `r`

to their respective maximum, and `max_l`

and `max_r`

to the current maximum for the left and right pointers.

The `while`

loop will run until `l`

meets or exceeds `r.`

During each loop, check the list’s current maximums at the left and right sides.

If the right maximum is smaller, decrement r, and check if the current right maximum

`max_r`

is larger than the new element at`r.`

- If the new element is larger, replace the maximum right with the new element.
- Else, update
`trapped_water`

; this is because the`max_l`

is larger than`max_r`

and`max_r`

is larger than the new element at`r`

; therefore, add the difference between the`max_r`

and the element at`r`

.

Else, perform steps similar to the first conditional statement except interchange all left and right values and increment

`l`

instead of decrementing.

Once the `while`

loop exists, `return trapped_water`

.

## Algorithm Description

**Two Pointer Algorithm -** An algorithm typically used to search a list where opposite ends of the list share a relationship that will be compared to determine some outcome.

For this problem, that condition would be if the maximum left element is less than the maximum right element.

**Visual Examples**

The two-pointer algorithm being performed on a list where the condition summing to 6, click to view

## Solution

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

class Solution:
def trap(self, height: List[int]) -> int:
trapped_water = 0
l, r = 0, len(height) - 1
max_l, max_r = height[l], height[r]
while l < r:
if max_l >= max_r:
r -= 1
if height[r] >= max_r:
max_r = height[r]
else:
trapped_water += max_r - height[r]
else:
l += 1
if height[l] >= max_l:
max_l = height[l]
else:
trapped_water += max_l - height[l]
return trapped_water