Depth-First Search
Pacific Atlantic Water Flow
DESCRIPTION (inspired by Leetcode.com)
You are given an m x n matrix of non-negative integers representing a grid of land, where rain falls on every cell. Each value in the grid represents the height of that piece of land.
The Pacific Ocean touches the left and top edges of the matrix, while the Atlantic Ocean touches the right and bottom edges. Water can only flow from a cell to its neighboring cells directly north, south, east, or west, but only if the height of the neighboring cell is equal to or lower than the current cell.
Write a function to return a list of grid coordinates (i, j) where water can flow to both the Pacific and Atlantic Oceans. Water can flow from all cells directly adjacent to the ocean into that ocean.
Example 1:
Input:
grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
Output:
[ [0, 2], [1, 2], [2, 0], [2, 1], [2, 2] ]
public class Solution {
public List<List<Integer>> pacific_atlantic_flow(int[][] grid) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
To solve this question, we need to traverse the grid to find all cells where water can flow to both the Pacific and Atlantic Oceans, and then find the cells that are contained in both those sets.
Approach 1: Brute Force Approach
Let's focus on how to find all the cells that are reachable from an ocean. One straightforward approach is to iterate over each cell in the graph, and then check if there is a valid path from that cell to the ocean. If there is, we can add it to a set (depending on if it reaches the Pacific or Atlantic Ocean). After iterating over each cell, we can return the intersection of those two sets.
class Solution {int rows, cols;int[][] matrix;Set<String> pacific = new HashSet<>();Set<String> atlantic = new HashSet<>();public List<List<Integer>> pacificAtlantic(int[][] matrix) {if (matrix == null || matrix.length == 0) {return new ArrayList<>();}this.matrix = matrix;this.rows = matrix.length;this.cols = matrix[0].length;// Perform full DFS from each cell.for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {Set<String> visited = new HashSet<>();dfs(r, c, r, c, visited);}}List<List<Integer>> result = new ArrayList<>();for (String cell : pacific) {if (atlantic.contains(cell)) {String[] parts = cell.split(",");result.add(Arrays.asList(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])));}}return result;}private void dfs(int startR, int startC, int r, int c, Set<String> visited) {String key = r + "," + c;if (visited.contains(key)) {return;}visited.add(key);if (r == 0 || c == 0) {pacific.add(startR + "," + startC);}if (r == rows - 1 || c == cols - 1) {atlantic.add(startR + "," + startC);}int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (int[] dir : directions) {int nr = r + dir[0], nc = c + dir[1];if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] <= matrix[r][c]) {dfs(startR, startC, nr, nc, visited);visited.remove(nr + "," + nc);}}}}
The problem with this approach is that it is very inefficient. For each cell, we have to perform a full DFS traversal of the entire grid in the worst case, resulting in a run-time of O((m x n)2).
Approach 2: Boundary DFS
The brute-force approach is inefficient because there is a lot of repeat work being done. For example, we have to calculate parts of the same path multiple times as we check if there is a valid path from a cell to the ocean.
A more efficient approach is to use "boundary DFS". With this approach, we "invert" the problem by starting from all cells adjacent to each ocean, and then use DFS to find cells that can flow into that cell. All the cells that we visit during each of these traversals are the set of cells that can flow into the ocean that the DFS originated from.
This is more efficient because it reduces redundant work - once we visit a cell using this traversal, we can mark it as visited so it is not visited by future traversals.
At the end, we can return the intersection of both sets to get the final answer.
Solution
class Solution {int[][] grid;int rows, cols;public List<List<Integer>> pacificAtlanticFlow(int[][] grid) {if (grid == null || grid.length == 0) {return new ArrayList<>();}this.grid = grid;this.rows = grid.length;this.cols = grid[0].length;// Step 1: Initialize empty setsSet<String> pacificReachable = new HashSet<>();Set<String> atlanticReachable = new HashSet<>();// initializes DFS from all cells in the Atlantic and Pacific Oceans// Note how we share a single visited set// across DFS calls that originate from the same oceanfor (int r = 0; r < rows; r++) {dfs(r, 0, pacificReachable);dfs(r, cols - 1, atlanticReachable);}for (int c = 0; c < cols; c++) {dfs(0, c, pacificReachable);dfs(rows - 1, c, atlanticReachable);}// return the intersection of both sets.List<List<Integer>> result = new ArrayList<>();for (String cell : pacificReachable) {if (atlanticReachable.contains(cell)) {String[] parts = cell.split(",");result.add(Arrays.asList(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])));}}return result;}private void dfs(int r, int c, Set<String> reachable) {reachable.add(r + "," + c);int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};for (int[] dir : directions) {int nr = r + dir[0], nc = c + dir[1];if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {String key = nr + "," + nc;if (!reachable.contains(key) && grid[nr][nc] >= grid[r][c]) {dfs(nr, nc, reachable);}}}}}
What is the time complexity of this solution?
O(1)
O(2ⁿ)
O(n log n)
O(m * n)