Trapping Rain Water – Two Pointer Approach #leetcode-problem 42

The main idea is to use two pointers, one starting from the left and one starting from the right. Instead of calculating the maximum height on both sides for every element separately, we keep track of the maximum heights while moving the pointers towards each other.

We start with the left pointer at index 0 and the right pointer at the last index.

left = 0
right = len(height) - 1

We also keep a variable called unit to store the total amount of water trapped.

unit = 0

Initially, lmax stores the height at the leftmost position and rmax stores the height at the rightmost position.

lmax = height[left]
rmax = height[right]

Now we keep moving the pointers while left is less than right.

If lmax is smaller than rmax, we move the left pointer forward because the left side is the limiting boundary.

left += 1

After moving the pointer, we update lmax:

lmax = max(lmax, height[left])

Then the amount of water trapped at the current position is:

unit += lmax - height[left]

Similarly, if rmax is less than or equal to lmax, we move the right pointer backwards because the right side is now the limiting boundary.

right -= 1

Then update rmax:

rmax = max(rmax, height[right])

And calculate the water trapped at the current position:

unit += rmax - height[right]

The important point to remember is that we always move the pointer belonging to the side with the smaller maximum height. This works because the smaller boundary determines how much water can be trapped at that position.

We continue this process until the two pointers meet. Finally, unit contains the total amount of trapped water.

Leetcode Solution:

class Solution:
    def trap(self, height: List[int]) -> int:
        left = 0
        unit = 0
        right = len(height) - 1

        lmax = height[left]
        rmax = height[right]

        while left < right:
            if lmax < rmax:
                left += 1
                lmax = max(lmax, height[left])
                unit += lmax - height[left]

            elif rmax <= lmax:
                right -= 1
                rmax = max(rmax, height[right])
                unit += rmax - height[right]

        return unit