Given a matrix arr[][] of dimension M*N consisting of positive integers, where arr[i][j] represents the height of each unit cell, the task is to find the total volume of water trapped in the matrix after rain.
Examples:
Input: arr[][] = {{4, 2, 7}, {2, 1, 10}, {5, 10, 2}}
Output: 1
Explanation:
The rain water can be trapped in the following way:
- The cells, {(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)} traps 0 unit volume of rain water as all water goes out of the matrix as cells are on the boundary.
- The cell (2, 2) traps 1 unit volume of rain water in between the cells {(0, 1), (1, 0), (1, 2), and (2, 1)}.
Therefore, a total of 1 unit volume of rain water has been trapped inside the matrix.
Input: arr[][] = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}}
Output: 4
Approach: The given problem can be solved by using the Greedy Technique and Min-Heap. Follow the steps below to solve the problem:
- Initialize a Min-Heap using the priority_queue, say PQ, to store the pairs of positions of a cell and its height.
- Push all the boundary cells in the PQ and mark all the pushed cells as visited.
- Initialize two variables, say ans as 0 and maxHeight as 0 to store the total volume and the maximum height of all the cells in PQ respectively.
- Iterate until PQ is not empty and perform the following steps:
- Store the top node of PQ in a variable, say front, and erase the top element of PQ.
- Update the value of maxHeight as the maximum of maxHeight and front.height.
- Now, traverse to all the adjacent nodes of the current cell (front.X, front.Y) and do the following:
- If the adjacent cell is valid i.e, the cell is not out of bound and not yet visited, then, push the value of the adjacent cell into PQ.
- If the height of the adjacent cell is less than maxHeight then increment the ans by the difference of maxHeight and the height of the adjacent cell.
- Finally, after completing the above steps, print the value of ans as the resultant water trapped after rain.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the direction of all the// adjacent cellsvector<vector<int> > dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };// Node structurestruct node { int height; int x, y;};// Comparator function to implement// the min heap using priority queuestruct Compare { // Comparator function bool operator()(node const& a, node const& b) { return a.height > b.height; }};// Function to find the amount of water// the matrix is capable to holdint trapRainWater(vector<vector<int> >& heightMap){ int M = heightMap.size(); int N = heightMap[0].size(); // Stores if a cell of the matrix // is visited or not vector<vector<bool> > visited(M, vector<bool>(N, false)); // Initialize a priority queue priority_queue<node, vector<node>, Compare> pq; // Traverse over the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // If element is not on // the boundary if (!(i == 0 || j == 0 || i == M - 1 || j == N - 1)) continue; // Mark the current cell // as visited visited[i][j] = true; // Node for priority queue node t; t.x = i; t.y = j; t.height = heightMap[i][j]; // Pushe all the adjacent // node in the pq pq.push(t); } } // Stores the total volume int ans = 0; // Stores the maximum height int max_height = INT_MIN; // Iterate while pq is not empty while (!pq.empty()) { // Store the top node of pq node front = pq.top(); // Delete the top element of pq pq.pop(); // Update the max_height max_height = max(max_height, front.height); // Stores the position of the // current cell int curr_x = front.x; int curr_y = front.y; for (int i = 0; i < 4; i++) { int new_x = curr_x + dir[i][0]; int new_y = curr_y + dir[i][1]; // If adjacent cells are out // of bound or already visited if (new_x < 0 || new_y < 0 || new_x >= M || new_y >= N || visited[new_x][new_y]) { continue; } // Stores the height of the // adjacent cell int height = heightMap[new_x][new_y]; // If height of current cell // is smaller than max_height if (height < max_height) { // Increment the ans by // (max_height-height) ans = ans + (max_height - height); } // Define a new node node temp; temp.x = new_x; temp.y = new_y; temp.height = height; // Push the current node // in the pq pq.push(temp); // Mark the current cell // as visited visited[new_x][new_y] = true; } } return ans;}// Driver Codeint main(){ vector<vector<int> > arr = { { 1, 4, 3, 1, 3, 2 }, { 3, 2, 1, 3, 2, 4 }, { 2, 3, 3, 2, 3, 1 } }; cout << trapRainWater(arr); return 0;} |
Java
// Java Program for above approachimport java.util.*;// Node structureclass node { int height; int x, y;}// Comparator function to implement// the min heap using priority queueclass Compare implements Comparator<node> { public int compare(node a, node b) { return a.height - b.height; }}class Main { // Stores the direction of all the // adjacent cells static int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // Function to find the amount of water // the matrix is capable to hold static int trapRainWater(int[][] heightMap) { int M = heightMap.length; int N = heightMap[0].length; // Stores if a cell of the matrix // is visited or not boolean[][] visited = new boolean[M][N]; // Initialize a priority queue PriorityQueue<node> pq = new PriorityQueue<node>(new Compare()); // Traverse over the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // If element is not on // the boundary if (!(i == 0 || j == 0 || i == M - 1 || j == N - 1)) continue; // Mark the current cell // as visited visited[i][j] = true; // Node for priority queue node t = new node(); t.x = i; t.y = j; t.height = heightMap[i][j]; // Pushe all the adjacent // node in the pq pq.offer(t); } } // Stores the total volume int ans = 0; // Stores the maximum height int max_height = Integer.MIN_VALUE; // Iterate while pq is not empty while (!pq.isEmpty()) { // Store the top node of pq node front = pq.poll(); // Update the max_height max_height = Math.max(max_height, front.height); // Stores the position of the // current cell int curr_x = front.x; int curr_y = front.y; for (int i = 0; i < 4; i++) { int new_x = curr_x + dir[i][0]; int new_y = curr_y + dir[i][1]; // If adjacent cells are out // of bound or already visited if (new_x < 0 || new_y < 0 || new_x >= M || new_y >= N || visited[new_x][new_y]) { continue; } // Stores the height of the // adjacent cell int height = heightMap[new_x][new_y]; // If height of current cell // is smaller than max_height if (height < max_height) { // Increment the ans by // (max_height-height) ans = ans + (max_height - height); } // Define a new node node temp = new node(); temp.x = new_x; temp.y = new_y; temp.height = height; // Push the current node // in the pq pq.offer(temp); // Mark the current cell // as visited visited[new_x][new_y] = true; } } return ans; } // Driver code public static void main(String[] args) { int[][] arr = { { 1, 4, 3, 1, 3, 2 }, { 3, 2, 1, 3, 2, 4 }, { 2, 3, 3, 2, 3, 1 } }; System.out.println(trapRainWater(arr)); }}// This code is contributed by codebraxnzt |
Python3
# Python Code# Stores the direction of all the# adjacent cellsdir = [[-1, 0], [0, 1], [1, 0], [0, -1]]# Node structureclass Node: def __init__(self, height, x, y): self.height = height self.x = x self.y = y# Comparator function to implement# the min heap using priority queueclass Compare: # Comparator function def __lt__(self, a, b): return a.height > b.height# Function to find the amount of water# the matrix is capable to holddef trapRainWater(heightMap): M = len(heightMap) N = len(heightMap[0]) # Stores if a cell of the matrix # is visited or not visited = [[False for _ in range(N)] for _ in range(M)] # Initialize a priority queue pq = [] # Traverse over the matrix for i in range(M): for j in range(N): # If element is not on # the boundary if i == 0 or j == 0 or i == M - 1 or j == N - 1: visited[i][j] = True # Node for priority queue t = Node(heightMap[i][j], i, j) # Pushe all the adjacent # node in the pq pq.append(t) # Stores the total volume ans = 0 # Stores the maximum height max_height = float('-inf') # Iterate while pq is not empty while pq: # Store the top node of pq front = pq.pop() # Update the max_height max_height = max(max_height, front.height) # Stores the position of the # current cell curr_x = front.x curr_y = front.y for i in range(4): new_x = curr_x + dir[i][0] new_y = curr_y + dir[i][1] # If adjacent cells are out # of bound or already visited if new_x < 0 or new_y < 0 or new_x >= M or new_y >= N or visited[new_x][new_y]: continue # Stores the height of the # adjacent cell height = heightMap[new_x][new_y] # If height of current cell # is smaller than max_height if height < max_height: # Increment the ans by # (max_height-height) ans += (max_height - height) # Define a new node temp = Node(height, new_x, new_y) # Push the current node # in the pq pq.append(temp) # Mark the current cell # as visited visited[new_x][new_y] = True return ans# Driver Codearr = [[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]]print(trapRainWater(arr)) |
C#
using System;using System.Collections.Generic;class Gfg{ // Stores the direction of all the // adjacent cells static int[] dx = { -1, 0, 1, 0 }; static int[] dy = { 0, 1, 0, -1 }; static int TrapRainWater(int[][] heightMap) { int M = heightMap.Length; int N = heightMap[0].Length; var visited = new bool[M, N]; // Initialize a sorted set var pq = new SortedSet<(int, int, int)>(); // Traverse over the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // If element is not on the boundary if (!(i == 0 || j == 0 || i == M - 1 || j == N - 1)) continue; // Mark the current cell as visited visited[i, j] = true; // Tuple for sorted set var t = (heightMap[i][j], i, j); // Pushe all the adjacent nodes in the pq pq.Add(t); } } // Stores the total volume int ans = 0; // Stores the maximum height int maxHeight = int.MinValue; // Iterate while pq is not empty while (pq.Count > 0) { // Store the top node of pq var front = pq.Min; // Delete the top element of pq pq.Remove(front); // Update the maxHeight maxHeight = Math.Max(maxHeight, front.Item1); // Stores the position of the current cell int curr_x = front.Item2; int curr_y = front.Item3; for (int i = 0; i < 4; i++) { int new_x = curr_x + dx[i]; int new_y = curr_y + dy[i]; // If adjacent cells are out of bound or already visited if (new_x < 0 || new_y < 0 || new_x >= M || new_y >= N || visited[new_x, new_y]) continue; // Stores the height of the adjacent cell int height = heightMap[new_x][new_y]; // If height of current cell is smaller than maxHeight if (height < maxHeight) { // Increment the ans by (maxHeight - height) ans = ans + (maxHeight - height); } // Tuple for sorted set var temp = (height, new_x, new_y); // Push the current node in the pq pq.Add(temp); // Mark the current cell as visited visited[new_x, new_y] = true; } } return ans; } static void Main(string[] args) { int[][] arr = new int[3][]; arr[0] = new int[] { 1, 4, 3, 1, 3, 2 }; arr[1] = new int[] { 3, 2, 1, 3, 2, 4 }; arr[2] = new int[] { 2, 3, 3, 2, 3, 1 }; Console.WriteLine(TrapRainWater(arr)); }} |
Javascript
// Define directions arrayconst dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];// Node structureclass Node { constructor(height, x, y) { this.height = height; this.x = x; this.y = y; }}// Comparator function to implement// the min heap using priority queueclass Compare { // Comparator function static compare(a, b) { return a.height > b.height; }}// Function to find the amount of water// the matrix is capable to holdfunction trapRainWater(heightMap) { const M = heightMap.length; const N = heightMap[0].length; // Stores if a cell of the matrix // is visited or not const visited = new Array(M).fill(false).map(() => new Array(N).fill(false)); // Initialize a priority queue const pq = []; // Traverse over the matrix for (let i = 0; i < M; i++) { for (let j = 0; j < N; j++) { // If element is not on // the boundary if (i === 0 || j === 0 || i === M - 1 || j === N - 1) { visited[i][j] = true; // Node for priority queue const t = new Node(heightMap[i][j], i, j); // Push all the adjacent // node in the pq pq.push(t); } } } // Stores the total volume let ans = 0; // Stores the maximum height let max_height = -Infinity; // Iterate while pq is not empty while (pq.length) { // Store the top node of pq const front = pq.pop(); // Update the max_height max_height = Math.max(max_height, front.height); // Stores the position of the // current cell const curr_x = front.x; const curr_y = front.y; for (let i = 0; i < 4; i++) { const new_x = curr_x + dir[i][0]; const new_y = curr_y + dir[i][1]; // If adjacent cells are out // of bound or already visited if (new_x < 0 || new_y < 0 || new_x >= M || new_y >= N || visited[new_x][new_y]) { continue; } // Stores the height of the // adjacent cell const height = heightMap[new_x][new_y]; // If height of current cell // is smaller than max_height if (height < max_height) { // Increment the ans by // (max_height-height) ans += (max_height - height); } // Define a new node const temp = new Node(height, new_x, new_y); // Push the current node // in the pq pq.push(temp); // Mark the current cell // as visited visited[new_x][new_y] = true; } } return ans;}// Driver Codeconst arr = [[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]];console.log(trapRainWater(arr)) |
Output
4
Time Complexity: (N * M * log(N * M))
Auxiliary Space: O(N * M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
