Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach: Priority Queue
3.1.
Implementation
3.2.
Analysis of Complexity
4.
Frequently Asked Questions
4.1.
What is the motive behind the problem of Trapping rainwater in a matrix?
4.2.
What do you mean by Priority Queue?
4.3.
What is the time complexity to solve this problem?
5.
Conclusion
Last Updated: Mar 27, 2024

Trapping Rain Water in a Matrix

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

What do you mean by a matrix? A matrix is a two-dimensional structure identified by two indices, one for rows and another for columns. Every matrix is a two-dimensional array but not vice versa. 

Trapping rainwater is a famous and routine question asked in interviews with many companies like Google, Amazon, Samsung, Adobe, etc. This particular problem we will be heading to is the topic matrix. The matrix will contain the height of each cell that can hold the rainwater, and we have to return the total volume of water it can trap after rain.

 

Let’s move to our problem statement for better understanding so that you can think of the appropriate approach to solve the problem.

Also check out Data Structures

 

Problem Statement

 

So the problem statement is pretty simple, we are given an m x n matrix of positive integers where each element of the matrix represents the height of the bars; we aim to find the total volume of water trapped in the matrix after rain.

Let’s understand the idea of how to solve this problem through an example.

 

matrix

 

This is like a container, and the water-filled in the container will be till the minimum boundary.

So in this container, first, I will be processing the outside boundaries because everything will be stored inside these boundaries, and slowly, I will push in the boundary.

 

matrix

 

After visiting the boundary, we can see that the minimum value we are getting from here is ‘1’.

After visiting ‘1’, we will reduce the boundary and include ‘13’ into the boundary.

 

matrix

 

The minimum boundary value is ‘12’ and updates the minimum value from ‘1’ to ‘12’.

 

We will push the boundary by checking the adjacent of each boundary having a value as ‘12’. If the adjacent ‘12’ is already inside the boundary, it will do nothing; otherwise, add the boundary if the boundary value is greater than ‘12’.

 

If the adjacent boundary value is less than ‘12’, then water will be filled inside that boundary. The amount of water-filled will be the minimum value of boundary - value of adjacent boundary(12-10=2).

 

matrix

 

The adjacent boundary of ‘10’ left outside is also less than ‘12’, i.e., ‘8’. So the amount of water filled will be 12 - 8 = 4.

 

The adjacent boundary of ‘8’ left outside the boundary is also less than ‘12’, i.e., ‘4’. So the amount of water filled will be 12 - 4 = 8.

 

matrix

 

The total amount of rainwater trapped will be 2+4+8=14

 

Now the minimum boundary value will get updated to ‘13’ and check for the adjacent boundaries that are unvisited or visited.

 

matrix

 

We can see that all the adjacent boundaries of ‘13’ are visited. So will get the total volume of rainwater trapped in between the bars after rain.

 

Note: Please try to solve Trapping rainwater in a matrix on Coding Ninjas Studio before heading into the solution.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

 

 

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 WaterContainer 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:

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.

Previous article
Minimum Difference Between Maximum and Minimum Value of Array with Given Operations
Next article
Heap Sort for Decreasing Order Using Min-Heap
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass