Leetcode Trapping Rain Water II problem solution

from heapq import heappush, heappop, heapify


class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        mlen = len(heightMap)
        if mlen == 0:
            return 0
        nlen = len(heightMap[0])
        if nlen == 0:
            return 0

        HEAP = []
        visited = [[False for _ in range(nlen)] for _ in range(mlen)]
        for i, height in enumerate(heightMap[0]):
            HEAP.append(Tile(0, i, height))
            visited[0][i] = True
        for i, height in enumerate(heightMap[-1]):
            HEAP.append(Tile(mlen - 1, i, height))
            visited[-1][i] = True
        for i in range(mlen):
            HEAP.append(Tile(i, 0, heightMap[i][0]))
            HEAP.append(Tile(i, nlen - 1, heightMap[i][-1]))
            visited[i][0] = True
            visited[i][-1] = True
        heapify(HEAP)

        res = 0
        while HEAP:
            tile = heappop(HEAP)
            m, n, h = tile.m, tile.n, tile.h
            if m < mlen - 1 and not visited[m + 1][n]:
                visited[m + 1][n] = True
                res += max(h - heightMap[m + 1][n], 0)
                heappush(HEAP, Tile(m + 1, n, max(h, heightMap[m + 1][n])))

            if tile.m > 0 and not visited[m - 1][n]:
                visited[m - 1][n] = True
                res += max(h - heightMap[m - 1][n], 0)
                heappush(HEAP, Tile(m - 1, n, max(h, heightMap[m - 1][n])))

            if n < nlen - 1 and not visited[m][n + 1]:
                visited[m][n + 1] = True
                res += max(h - heightMap[m][n + 1], 0)
                heappush(HEAP, Tile(m, n + 1, max(h, heightMap[m][n + 1])))

            if n > 0 and not visited[m][n - 1]:
                visited[m][n - 1] = True
                res += max(h - heightMap[m][n - 1], 0)
                heappush(HEAP, Tile(m, n - 1, max(h, heightMap[m][n - 1])))
        return res


class Tile:
    def __init__(self, m, n, h):
        self.m = m
        self.n = n
        self.h = h

    def __lt__(self, other):
        if self.h < other.h:
            return True
        elif self.h > other.h:
            return False
        else:
            if self.m < other.m:
                return True
            elif self.m > other.m:
                return False
            else:
                return self.n < other.n

class Solution {
    
     class Coordinates{
        int row;
        int col;
        
        public Coordinates(int r, int c){
            this.row = r;
            this.col = c;
        }
        
    }

    int[] top =    {0, 0, 1, -1};
    int[] bottom = {1,-1, 0, 0};
    
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        
        boolean [][] visited = new boolean[m][n];

        PriorityQueue<Coordinates> pq = new PriorityQueue<Coordinates>(
            (a,b) -> heightMap[a.row][a.col] - heightMap[b.row][b.col]);
        
        int water = 0;
        pushToQueue(pq, heightMap, visited, m, n);
        int max = Integer.MIN_VALUE;

        while(pq.size()>0)
        {
            Coordinates element = pq.poll();
            int x = element.row;
            int y = element.col;
            int val = heightMap[x][y];
            
            max = Math.max(max, val);
            
            for(int i=0;i<4;i++)
            {
                int t = x + top[i];
                int b = y + bottom[i];
                
                if(t<0 || t>=m || b<0 || b>=n || visited[t][b])
                    continue;
                pq.offer(new Coordinates(t,b));
                visited[t][b] = true;
            }
            
            if(heightMap[x][y] < max)
                water += max - heightMap[x][y];
        }
        return water;
    }

    void pushToQueue(PriorityQueue<Coordinates> pq, int [][]heightMap, 
                     boolean[][] visited,int m, int n)
    {
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0 || j==0 || i == m-1 || j==n-1)
                {
                    pq.offer(new Coordinates(i,j));
                    visited[i][j] = true;
                }
            }
        }
    }
    
}

class Solution {
    
public:
 
    int minaround(int i, int j, vector<vector<int>>& water){
        int n = water.size();
        int m = water[0].size();
        int min_num = water[i][j];
       if(i-1>=0)
           min_num = min(min_num,water[i-1][j]);
        if(j-1>=0)
            min_num = min(min_num,water[i][j-1]);
        if(i+1<n)
           min_num = min(min_num,water[i+1][j]);
        if(j+1<m)
            min_num = min(min_num,water[i][j+1]);
        if(i==n-1||i==0||j==m-1||j==0) min_num=0;
       
        return min_num;
        
    }
    
    void flowout(int i, int j, vector<vector<int>> &water, vector<vector<int>>& heightMap){
       
        if(i<0||j<0) return;
        int n = heightMap.size();
        int m = heightMap[0].size();
        if(i>=n||j>=m) return;
        int level = max(minaround(i,j,water),heightMap[i][j]);
                if(level<water[i][j]){
                    water[i][j] = level;
                    flowout(i,j+1,water,heightMap);
                    flowout(i,j-1,water,heightMap);
                    flowout(i+1,j,water,heightMap);
                    flowout(i-1,j,water,heightMap);   
                }
        return;
    }
    int trapRainWater(vector<vector<int>>& heightMap) {
        
        int n = heightMap.size();
        int m = heightMap[0].size();

        vector<vector<int>> water(n,vector<int>(m,20000));
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                flowout(i,j,water,heightMap);      
            }
        }
        int ans = 0;
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                ans = ans + water[i][j] - heightMap[i][j];
            }
        }
        
        return ans;
    }
};