42. Trapping Rain Water

class Solution:
    def trap(self, a: List[int]) -> int:
        n=len(a)
        l,r=0,n-1
        lmax,rmax=0,0
        ans=0
        while l<r:
            '''
            Why dont we need rmax .2 cases here
            1)Because lets say there is a bar greater than a[l] in between l,n-1
            then lmax should be min(lmax,rmax)
            2)Lets say tere is no bar greater than a[l] in bertween l and n-1,the obviously a[r] will be max as we moved to
            l in while block. See code for more understanding.
            '''
            if a[l]<a[r]:
                lmax=max(lmax,a[l])
                ans+=lmax-a[l]
                l+=1

            else:
                rmax=max(rmax,a[r])
                ans+=rmax-a[r]
                r-=1
        return ans
class Solution:
    def trap(self, a: List[int]) -> int:

        n=len(a)
        left,right=[0]*n,[0]*n
        left[0]=a[0]
        right[-1]=a[-1]
        for i in range(1,n):
            left[i]=max(a[i],left[i-1])

        for i in range(n-2,-1,-1):
            right[i]=max(right[i+1],a[i])
        ans=0
        for i in range(n):
            ans+=(min(left[i],right[i])-a[i])
        return ans

#trapping rain water 2
import heapq as hq
class Solution:
    def trapRainWater(self, h: List[List[int]]) -> int:
        q=[]
        m,n=len(h),len(h[0])
        vis=[[False]*n for i in range(m)]

        for i in range(m):
            for j in range(n):
                if i==0 or j==0 or i==m-1 or j==n-1:
                    q.append((h[i][j],i,j))
                    vis[i][j]=True

        hq.heapify(q)
        ans=0
        while q:
            t,i,j=hq.heappop(q)
            for u,v in (0,1),(1,0),(0,-1),(-1,0):
                x,y=i+u,j+v
                if 0<=x<m and 0<=y<n and vis[x][y]==False:
                    if h[x][y]>=t:
                        hq.heappush(q,(h[x][y],x,y))
                    else:
                        ans+=(t-h[x][y])
                        hq.heappush(q,(t,x,y))
                    vis[x][y]=True
        return ans