There is an N x M rectangular island that borders both the Pacific Ocean and the Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.
The island is partitioned into a grid of square cells. The island receives a lot of rain, and the rainwater can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.
Given a matrix mat[][] having N rows and M columns where mat[x][y] represents the height above sea level of the cell at coordinate (x, y), the task is to find the number of coordinates (x, y) such that the rainwater can flow from the cell (x, y) to both the Pacific and Atlantic oceans.
Example:
Input: mat[][] = {{1, 2, 2, 3, 5},
{3, 2, 3, 4, 4},
{2, 4, 5, 3, 1},
{6, 7, 1, 4, 5},
{5, 1, 1, 2, 4}}Output: 7
Explanation: In the given matrix, there are 7 coordinates through which the water can flow to both the lakes. They are (0, 4), (1, 3), (1, 4), (2, 2), (3, 0), (3, 1), and (4, 0)Input: mat[][] = {{2, 2},
{2, 2}}
Output: 4
Example: In the following example, all cells allow water to flow to both the lakes.
Approach: The given problem can be solved using either a DFS or a BFS traversal. The idea is to mark all the cells that are reachable from the directly connected cells from the Pacific and the Atlantic Oceans separately using either DFS or BFS. The count of cells that are connected through both is the required answer. Below are the steps to follow:
- Create two queues q1 and q2 in order to store the coordinates of the matrix as a pair.
- Traverse the whole matrix and store coordinates directly connected to the Pacific Ocean to q1 and perform a BFS traversal from all the coordinates in q1 and mark them visited.
- Similarly, traverse the whole matrix and store coordinates directly connected to the Atlantic Ocean to q2 and perform a BFS traversal from all the coordinates in q2 and mark them visited.
- Traverse the given matrix mat[][] and maintain the count of coordinates that are visited during both the traversals.
Below is the implementation of the above approach:
C++
// C++ Program of the above approach #include <bits/stdc++.h> using namespace std; int x[5] = { 0, 0, -1, 1 }; int y[5] = { 1, -1, 0, 0 }; // Function to check if coordinate // (i, j) lies inside N x M matrix bool safe(int i, int j, int N, int M) { if (i < 0 || j < 0 || i >= N || j >= M) return false; return true; } // Function to perform a BFS // Traversal and mark visited void BFS(vector<vector<int> > matrix, int N, int M, queue<pair<int, int> > q, vector<vector<bool> >& vis) { // Loop to traverse q while (q.empty() == false) { // Stores current coordinate pair<int, int> cur = q.front(); q.pop(); // Mark current visited vis[cur.first][cur.second] = true; for (int i = 0; i < 4; i++) { int nx = cur.first + x[i]; int ny = cur.second + y[i]; // If coordinate (nx, ny) // is inbound and rechable if (safe(nx, ny, N, M) && matrix[nx][ny] >= matrix[cur.first] [cur.second] && vis[nx][ny] == false) { // Insert into queue q.push({ nx, ny }); // Mark visited vis[nx][ny] = true; } } } } // Function to find the count of // valid coordinates int countCoordinates(vector<vector<int> > mat, int N, int M) { // Queue to perform BFS queue<pair<int, int> > q1, q2; // Stores the visited coordinates // during the 1st traversal vector<vector<bool> > visited1( N, vector<bool>(M, false)); // Stores the visited coordinates // during the 2nd traversal vector<vector<bool> > visited2( N, vector<bool>(M, false)); // Insert the coordinates // directly connected for (int i = 0; i < M; i++) { q1.push({ 0, i }); q2.push({ N - 1, i }); } for (int j = 0; j < N - 1; j++) { q1.push({ j + 1, 0 }); q2.push({ j, M - 1 }); } // BFS for the 1st ocean BFS(mat, N, M, q1, visited1); // BFS for the 2nd ocean BFS(mat, N, M, q2, visited2); // Stores the required count int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // If coordinate (i, j) // is reachable from both if (visited1[i][j] && visited2[i][j]) { // Update count ans++; } } } // Return Answer return ans; } // Driver code int main() { vector<vector<int> > mat = { { 1, 2, 2, 3, 5 }, { 3, 2, 3, 4, 4 }, { 2, 4, 5, 3, 1 }, { 6, 7, 1, 4, 5 }, { 5, 1, 1, 2, 4 } }; cout << countCoordinates(mat, mat.size(), mat[0].size()); return 0; } |
Java
// Java Program of the above approach import java.util.*; class GFG{ static int x[] = { 0, 0, -1, 1 }; static int y[] = { 1, -1, 0, 0 }; static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to check if coordinate // (i, j) lies inside N x M matrix static boolean safe(int i, int j, int N, int M) { if (i < 0 || j < 0 || i >= N || j >= M) return false; return true; } // Function to perform a BFS // Traversal and mark visited static void BFS(int[][] matrix, int N, int M, Queue<pair> q, boolean [][]vis) { // Loop to traverse q while (q.isEmpty() == false) { // Stores current coordinate pair cur = q.peek(); q.remove(); // Mark current visited vis[cur.first][cur.second] = true; for (int i = 0; i < 4; i++) { int nx = cur.first + x[i]; int ny = cur.second + y[i]; // If coordinate (nx, ny) // is inbound and rechable if (safe(nx, ny, N, M) && matrix[nx][ny] >= matrix[cur.first] [cur.second] && vis[nx][ny] == false) { // Insert into queue q.add(new pair( nx, ny )); // Mark visited vis[nx][ny] = true; } } } } // Function to find the count of // valid coordinates static int countCoordinates(int[][] mat, int N, int M) { // Queue to perform BFS Queue<pair > q1 =new LinkedList<>(); Queue<pair > q2 =new LinkedList<>(); // Stores the visited coordinates // during the 1st traversal boolean visited1[][] = new boolean[N][M]; // Stores the visited coordinates // during the 2nd traversal boolean visited2[][] = new boolean[N][M]; // Insert the coordinates // directly connected for (int i = 0; i < M; i++) { q1.add(new pair( 0, i )); q2.add(new pair( N - 1, i )); } for (int j = 0; j < N - 1; j++) { q1.add(new pair( j + 1, 0 )); q2.add(new pair( j, M - 1 )); } // BFS for the 1st ocean BFS(mat, N, M, q1, visited1); // BFS for the 2nd ocean BFS(mat, N, M, q2, visited2); // Stores the required count int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // If coordinate (i, j) // is reachable from both if (visited1[i][j] && visited2[i][j]) { // Update count ans++; } } } // Return Answer return ans; } // Driver code public static void main(String[] args) { int[][] mat = { { 1, 2, 2, 3, 5 }, { 3, 2, 3, 4, 4 }, { 2, 4, 5, 3, 1 }, { 6, 7, 1, 4, 5 }, { 5, 1, 1, 2, 4 } }; System.out.print(countCoordinates(mat, mat[0].length, mat[1].length)); } } // This code contributed by shikhasingrajput |
Python3
Steps = [ [-1,0], # Up [0,1], # Right [1,0], # bottom [0,-1] # Left ] def withinLimits(row_num, col_num, total_rows, total_cols): if 0 <= row_num < total_rows and 0 <= col_num < total_cols: return True return False def waterSlope(oceanMatrix, matrix, row, col): nrows, ncols = len(matrix), len(matrix[0]) for i in Steps: if withinLimits(row+i[0], col+i[1], nrows, ncols): if matrix[row+i[0]][col+i[1]] >= matrix[row][col] and not oceanMatrix[row+i[0]][col+i[1]]: oceanMatrix[row+i[0]][col+i[1]] = True waterSlope(oceanMatrix, matrix, row+i[0], col+i[1]) def commonWaterFlow(matrix): matrix_rows = len(matrix) matrix_cols = len(matrix[0]) pacificMatrix = [[False for _ in range(matrix_cols)] for _ in range(matrix_rows)] atlanticMatrix = [[False for _ in range(matrix_cols)] for _ in range(matrix_rows)] pacificMatrix[0][1] = True pacificMatrix[0][2] = True for i in range(matrix_cols): pacificMatrix[0][i] = True atlanticMatrix[(matrix_rows-1)][i] = True for i in range(matrix_rows): pacificMatrix[i][0] = True atlanticMatrix[i][(matrix_cols-1)] = True for i in range(matrix_cols): waterSlope(pacificMatrix, matrix, 0, i) waterSlope(atlanticMatrix, matrix, matrix_rows-1, i) for i in range(matrix_rows): waterSlope(pacificMatrix, matrix, i, 0) waterSlope(atlanticMatrix, matrix, i, matrix_cols-1) Count = 0 for i in range(matrix_rows): for j in range(matrix_cols): if pacificMatrix[i][j] and atlanticMatrix[i][j]: Count += 1 return Count mat = [ [ 1, 2, 2, 3, 5 ], # T-T-T-T-T F-F-F-F-T [ 3, 2, 3, 4, 4 ], # T-T-T-T-T F-F-F-T-T [ 2, 4, 5, 3, 1 ], # T-T-T-F-F F-F-T-T-T [ 6, 7, 1, 4, 5 ], # T-T-F-F-F T-T-T-T-T [ 5, 1, 1, 2, 4 ] ] # T-F-F-F-F T-T-T-T-T print(commonWaterFlow(mat)) |
C#
// C# Program of the above approach using System; using System.Collections.Generic; public class GFG{ static int []x = { 0, 0, -1, 1 }; static int []y = { 1, -1, 0, 0 }; class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to check if coordinate // (i, j) lies inside N x M matrix static bool safe(int i, int j, int N, int M) { if (i < 0 || j < 0 || i >= N || j >= M) return false; return true; } // Function to perform a BFS // Traversal and mark visited static void BFS(int[,] matrix, int N, int M, Queue<pair> q, bool [,]vis) { // Loop to traverse q while (q.Count!=0 ) { // Stores current coordinate pair cur = q.Peek(); q.Dequeue(); // Mark current visited vis[cur.first,cur.second] = true; for (int i = 0; i < 4; i++) { int nx = cur.first + x[i]; int ny = cur.second + y[i]; // If coordinate (nx, ny) // is inbound and rechable if (safe(nx, ny, N, M) && matrix[nx,ny] >= matrix[cur.first,cur.second] && vis[nx,ny] == false) { // Insert into queue q.Enqueue(new pair( nx, ny )); // Mark visited vis[nx,ny] = true; } } } } // Function to find the count of // valid coordinates static int countCoordinates(int[,] mat, int N, int M) { // Queue to perform BFS Queue<pair > q1 =new Queue<pair >(); Queue<pair > q2 =new Queue<pair >(); // Stores the visited coordinates // during the 1st traversal bool [,]visited1 = new bool[N,M]; // Stores the visited coordinates // during the 2nd traversal bool [,]visited2 = new bool[N,M]; // Insert the coordinates // directly connected for (int i = 0; i < M; i++) { q1.Enqueue(new pair( 0, i )); q2.Enqueue(new pair( N - 1, i )); } for (int j = 0; j < N - 1; j++) { q1.Enqueue(new pair( j + 1, 0 )); q2.Enqueue(new pair( j, M - 1 )); } // BFS for the 1st ocean BFS(mat, N, M, q1, visited1); // BFS for the 2nd ocean BFS(mat, N, M, q2, visited2); // Stores the required count int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // If coordinate (i, j) // is reachable from both if (visited1[i,j] && visited2[i,j]) { // Update count ans++; } } } // Return Answer return ans; } // Driver code public static void Main(String[] args) { int[,] mat = { { 1, 2, 2, 3, 5 }, { 3, 2, 3, 4, 4 }, { 2, 4, 5, 3, 1 }, { 6, 7, 1, 4, 5 }, { 5, 1, 1, 2, 4 } }; Console.Write(countCoordinates(mat, mat.GetLength(0), mat.GetLength(1))); } } // This code contributed by shikhasingrajput |
Javascript
const Steps = [ [-1, 0], // Up [0, 1], // Right [1, 0], // Bottom [0, -1] // Left ]; function withinLimits(row_num, col_num, total_rows, total_cols) { return row_num >= 0 && row_num < total_rows && col_num >= 0 && col_num < total_cols; } function waterSlope(oceanMatrix, matrix, row, col) { const nrows = matrix.length, ncols = matrix[0].length; for (const [r, c] of Steps) { if (withinLimits(row+r, col+c, nrows, ncols)) { if (matrix[row+r][col+c] >= matrix[row][col] && !oceanMatrix[row+r][col+c]) { oceanMatrix[row+r][col+c] = true; waterSlope(oceanMatrix, matrix, row+r, col+c); } } } } function commonWaterFlow(matrix) { const matrix_rows = matrix.length, matrix_cols = matrix[0].length; const pacificMatrix = Array.from({length: matrix_rows}, () => Array(matrix_cols).fill(false)); const atlanticMatrix = Array.from({length: matrix_rows}, () => Array(matrix_cols).fill(false)); pacificMatrix[0][1] = true; pacificMatrix[0][2] = true; for (let i = 0; i < matrix_cols; i++) { pacificMatrix[0][i] = true; atlanticMatrix[(matrix_rows-1)][i] = true; } for (let i = 0; i < matrix_rows; i++) { pacificMatrix[i][0] = true; atlanticMatrix[i][(matrix_cols-1)] = true; } for (let i = 0; i < matrix_cols; i++) { waterSlope(pacificMatrix, matrix, 0, i); waterSlope(atlanticMatrix, matrix, matrix_rows-1, i); } for (let i = 0; i < matrix_rows; i++) { waterSlope(pacificMatrix, matrix, i, 0); waterSlope(atlanticMatrix, matrix, i, matrix_cols-1); } let Count = 0; for (let i = 0; i < matrix_rows; i++) { for (let j = 0; j < matrix_cols; j++) { if (pacificMatrix[i][j] && atlanticMatrix[i][j]) { Count++; } } } return Count; } const mat = [ [1, 2, 2, 3, 5], // T-T-T-T-T F-F-F-F-T [3, 2, 3, 4, 4], // T-T-T-T-T F-F-F-T-T [2, 4, 5, 3, 1], // T-T-T-F-F F-F-T-T-T [6, 7, 1, 4, 5], // T-T-F-F-F T-T-T-T-T [5, 1, 1, 2, 4] // T-F-F-F-F T-T-T-T-T ]; console.log(commonWaterFlow(mat)); // This code is contributed by Prince Kumar |
Output
7
Time Complexity: O(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!
