Trapping Rain Water in a Matrix

Approach: Priority Queue

Priority queue gonna help us to store the minimum value of the boundary. Every element in the priority queue is assigned some priority, which will help fetch the minimum value more efficiently.

Implementation

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.List;

public class Trappingrainwater1 {

// To define the coordinate of the cells
class Pair{
        int x;
        int y;
        int height;
        public Pair(int x, int y, int height){
            this.x =x ;
            this.y =y;
            this.height = height;
        }
    }
    public int trapRainWater(int[][] mat) {
     // Base conditions
        if(mat == null || mat.length == 0 || mat[0].length == 0) 
         return 0;
        
        int m = mat.length;
        int n = mat[0].length;
        
        // To keep an update regarding the visited boundaries
        boolean[][] visited = new boolean[m][n];
        // To store the minimum value from the boundary
        PriorityQueue<Pair> pq = new PriorityQueue<>((a,b)->(a.height - b.height));
        
        // To process the boundaries
        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){
                    visited[i][j] = true;
                    pq.offer(new Pair(i,j,mat[i][j]));
                }
            }
        }
        // For the BFS traversal, we can go UP, DOWN, LEFT, and RIGHT.
        // To explore the adjacent cells we are creating the 2D direction matrix.
        int[][] dirs = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        // To store the total volume of rain water
        int res = 0;
        while(!pq.isEmpty()){
            Pair cur = pq.poll();
            for(int i = 0 ; i<dirs.length; i++){
                int newX = cur.x + dirs[i][0];
                int newY = cur.y + dirs[i][1];
                if(newX < 0 || newY <0 || newX>=m || newY>=n || visited[newX][newY]){
                    continue;
                }
                visited[newX][newY] = true;
                // When the neighour of the minimum boundary value is less than its value
                res += Math.max(0,cur.height - mat[newX][newY]);
                pq.offer(new Pair(newX,newY,Math.max(mat[newX][newY],cur.height)));
            }
            
            
        }
        return res;
    }
  }

You can also try this code with Online Java Compiler

Run Code

Analysis of Complexity

Time Complexity: row:matrix height, col: matrix width --> step1: O(rowcol log(2m+2n-4)) = O(rowcol log(m+n)).

Space Complexity: boolean matrix and PriorityQueue--> O(m*n)

Also Read, Prefix Sum Array

Frequently Asked Questions

What is the motive behind the problem of Trapping rainwater in a matrix?

Trapping rainwater means finding the total volume of water stored between the bars after rain.

What do you mean by Priority Queue?

A priority queue is the extension of the queue data structure where each element is associated with some priority. Through priority, vital data gets through faster.

What is the time complexity to solve this problem?

Time Complexity: (row * col * log(col * row))

Auxiliary Space: O(col * row)

Conclusion

In this article, we have covered the problem of Trapping rainwater in a matrix using a priority queue in the Java language. With the help of pictorial representations and examples, it will be clear to you. You can practice more questions similar to this like Trapping Rain Water, Container With Most Water, and many more. 

If you are not familiar with priority queues, you can visit Coding Ninjas Studio for more information.

Recommended Reading:

• Kth Smallest Pair Sum in Given Array
• Kth Smallest Element in a Row Wise and Column Wise Sorted 2-D Array
• Application of Priority Queue
• Priority Queue using Java
• Practice Problems

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

For more practice, you can use Coding Ninjas Studio for various DSA questions typically asked in interviews. It will help you in mastering efficient coding techniques.