Problem Description

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:

42.Rainwatertrap.png

  • Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
  • Output: 6

My Idea

For each position in the resulting figure the amount of water that can be trapped is the minimum of the two highest peaks to the left and right minus the height at the position itself. To keep track of this we initiate pointers at both ends of the array and set the corresponding maximal values maxL and maxR. Until these two meet we do the following: We take the lower max value one and move it inwards by incrementing the pointer. At this point we need to calculate the amount of water that can be held in this position. We know what the min(maxL, maxR) is, since the corresponding pointer has just been moved, thus we need only subtract the height at this position from it and update the corresponding max value if needed. Negative numbers that result in the water calculation mean that no water can be held at this position. once the pointers meet we have checked the entire figure and can return the final amount of water.

My solution

# Time Complexity: O(n)
def trap(height: list[int])->int:
    l=0
    r=len(height)-1
    maxL=height[l]
    maxR=height[r]
    w=0
    while(l!=r):
       if(maxL<=maxR):
           l+=1
           w+=max(0,maxL-height[l])
           maxL=max(maxL,height[l])
       else:
           r-=1
           w+=max(0,maxR-height[r])
           maxR=max(maxR,height[r])
    return w