1.
Introduction
2.
Problem Statement
3.
Approach: Priority Queue
3.1.
Implementation
3.2.
Analysis of Complexity
4.
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

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

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.

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.

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).

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.

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.

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)

### 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.