Trapping Rain Water - Leetcode Solution

The Trapping Rain Water problem on LeetCode asks us to find the amount of water that can be trapped given a list of heights. Here's a step-by-step solution:

1. First, we need to identify the maximum height in the list. We'll call this max_height.

2. Create two pointers, left and right, at the beginning and end of the list respectively.

3. Create two variables, left_max and right_max, both initialized to 0.

4. Create a variable, water, initialized to 0.

5. While left is less than or equal to right:

a. If the height at the left pointer is less than or equal to the height at the right pointer:

i. If the height at the left pointer is greater than left_max, set left_max to the height at the left pointer.

ii. Otherwise, add left_max minus the height at the left pointer to the water variable, and move the left pointer to the right.

b. If the height at the left pointer is greater than the height at the right pointer:

i. If the height at the right pointer is greater than right_max, set right_max to the height at the right pointer.

ii. Otherwise, add right_max minus the height at the right pointer to the water variable, and move the right pointer to the left.

6. After the while loop, return the value of water.

Here's the Python code implementation:

def trap(height):
    max_height = max(height)
    left = 0
    right = len(height) - 1
    left_max = right_max = water = 0
    
    while left <= right:
        if height[left] <= height[right]:
            if height[left] > left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
                left += 1
        else:
            if height[right] > right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
                right -= 1
    
    return water

1