42. Trapping Rain Water

Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

The above elevation map 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.

Method 1: Two pointer O(n) time, O(1) space.

• Iterate the array from both ends using two pointers.
• Save the current right max and left max.
• Since when right max > left max, the water trapped depends on the left max, we then compare the current level with the left max. Then we increment the left pointer.

class Solution(object):
    def trap(self, height):
        left, lmax, rmax, right = 0, 0, 0, len(height) - 1
        res = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] < lmax:
                    res += (lmax - height[left])
                else:
                    lmax = height[left]

                left += 1
            else:
                if height[right] < rmax:
                    res += (rmax - height[right])
                else:
                    rmax = height[right]

                right -= 1
        return res