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]]
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: def pacificAtlantic(self, matrix): if not matrix or not matrix[0]: return [] rows, cols = len(matrix), len(matrix[0]) pacific = set() atlantic = set() # Try to find a path from r, c to the Pacific or Atlantic ocean # via neighboring cells with lower heights def dfs(start_r, start_c, r, c, visited): if (r, c) in visited: return visited[(r, c)] = True if r == 0 or c == 0: pacific.add((start_r, start_c)) if r == rows - 1 or c == cols - 1: atlantic.add((start_r, start_c)) directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] <= matrix[r][c]: dfs(start_r, start_c, nr, nc, visited) visited[(nr, nc)] = False # Perform full DFS from each cell. for r in range(rows): for c in range(cols): visited = {} dfs(r, c, r, c, visited) return list(pacific & atlantic)
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); } } }}
func pacificAtlantic(matrix [][]int) [][]int { if len(matrix) == 0 || len(matrix[0]) == 0 { return [][]int{} } rows, cols := len(matrix), len(matrix[0]) pacific := make(map[string]bool) atlantic := make(map[string]bool) var dfs func(startR, startC, r, c int, visited map[string]bool) dfs = func(startR, startC, r, c int, visited map[string]bool) { key := fmt.Sprintf("%d,%d", r, c) if visited[key] { return } visited[key] = true if r == 0 || c == 0 { pacific[fmt.Sprintf("%d,%d", startR, startC)] = true } if r == rows-1 || c == cols-1 { atlantic[fmt.Sprintf("%d,%d", startR, startC)] = true } directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} for _, dir := range directions { nr, nc := r+dir[0], c+dir[1] if nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] <= matrix[r][c] { dfs(startR, startC, nr, nc, visited) delete(visited, fmt.Sprintf("%d,%d", nr, nc)) } } } // Perform full DFS from each cell. for r := 0; r < rows; r++ { for c := 0; c < cols; c++ { visited := make(map[string]bool) dfs(r, c, r, c, visited) } } var result [][]int for cell := range pacific { if atlantic[cell] { parts := strings.Split(cell, ",") r, _ := strconv.Atoi(parts[0]) c, _ := strconv.Atoi(parts[1]) result = append(result, []int{r, c}) } } return result}
class Solution { pacificAtlantic(matrix: number[][]): number[][] { if (!matrix || !matrix[0]) { return []; } const rows = matrix.length, cols = matrix[0].length; const pacific = new Set<string>(); const atlantic = new Set<string>(); // Try to find a path from r, c to the Pacific or Atlantic ocean // via neighboring cells with lower heights function dfs(startR: number, startC: number, r: number, c: number, visited: Set<string>): void { const key = r + "," + c; if (visited.has(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); } const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; for (const [dr, dc] of directions) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] <= matrix[r][c]) { dfs(startR, startC, nr, nc, visited); visited.delete(nr + "," + nc); } } } // Perform full DFS from each cell. for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { const visited = new Set<string>(); dfs(r, c, r, c, visited); } } return Array.from(pacific).filter(cell => atlantic.has(cell)) .map(cell => cell.split(",").map(Number)); }}
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.
