Header Ad

Leetcode Trapping Rain Water II problem solution

In this Leetcode Trapping Rain Water II problem solution You are given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Leetcode Trapping Rain Water II problem solution


Problem solution in Python.

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



Problem solution in Java.

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;
                }
            }
        }
    }
    
}


Problem solution in C++.

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;
    }
};


Post a Comment

0 Comments