Day 19: Trapping Rain Water: Two Pointers - leetcode - Python3

 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

SOLUTION:

class Solution:

    def trap(self, height: List[int]) -> int:

        l, r= 0, len(height) -1

        maxL, maxR = height[l], height[r]

        result = 0

        while l < r:

           

            if maxL < maxR:

                l += 1

                maxL = max(maxL, height[l])

                result += maxL - height[l]

            else:

                r -= 1

                maxR = max(maxR, height[r])

                result += maxR - height[r]

        return result

Time Complexity: O(n)

Space Complexity:O(1)

How it works:

1. Initialize two pointers, l and r, to point to the beginning and end of the elevation map, respectively.
2. Initialize two variables, maxL and maxR, to the height of the bars at l and r, respectively.
3. Initialize a variable result to 0.
4. While l is less than r:
   • If maxL is less than maxR:
     • Increment l by 1.
     • Update maxL to the maximum of maxL and the height of the bar at l.
     • Add maxL - height[l] to result.
   • Otherwise:
     • Decrement r by 1.
     • Update maxR to the maximum of maxR and the height of the bar at r.
     • Add maxR - height[r] to result.
5. Return result.

The idea behind the code is to use two pointers to scan the elevation map from left to right and right to left, respectively. The maxL and maxR variables keep track of the maximum height of the bars to the left of l and to the right of r, respectively. The result variable keeps track of the total amount of water that can be trapped.