Lesson 146 of 250
417. Pacific Atlantic Water Flow
NeetCode: Pacific Atlantic Water Flow · LeetCode: 417. Pacific Atlantic Water Flow · Difficulty: Medium
An m x n grid holds the height of each cell. The Pacific Ocean touches the top and left edges, the Atlantic Ocean touches the bottom and right edges. Water flows from a cell to a neighbor (up, down, left, right) whose height is less than or equal to its own. Return every cell from which water can flow to both oceans.
Example
heights: 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: [0,4] [1,3] [1,4] [2,2] [3,0] [3,1] [4,0]The result is a List<List<Integer>> of [row, column] pairs. Both solutions add cells in row-major order, so the output order is fixed.
Brute force: search downhill from every cell
For every cell, run a flood fill that only moves to neighbors of height <= the current one, and see whether it touches a Pacific edge (row 0 or column 0) and an Atlantic edge (last row or last column). The same downhill regions are explored again for many start cells.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private boolean reachesBoth(int[][] h, int sr, int sc) {
int m = h.length;
int n = h[0].length;
boolean[][] visited = new boolean[m][n];
visited[sr][sc] = true;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{sr, sc});
boolean pacific = false;
boolean atlantic = false;
while (!stack.isEmpty()) {
int[] cell = stack.pop();
int r = cell[0];
int c = cell[1];
if (r == 0 || c == 0) {
pacific = true;
}
if (r == m - 1 || c == n - 1) {
atlantic = true;
}
for (int[] d : DIRS) {
int nr = r + d[0];
int nc = c + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
continue;
}
if (!visited[nr][nc] && h[nr][nc] <= h[r][c]) {
visited[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
return pacific && atlantic;
}
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> out = new ArrayList<>();
if (heights.length == 0 || heights[0].length == 0) {
return out;
}
for (int r = 0; r < heights.length; r++) {
for (int c = 0; c < heights[0].length; c++) {
if (reachesBoth(heights, r, c)) {
out.add(List.of(r, c));
}
}
}
return out;
}
}
public class Main {
public static void main(String[] args) {
Solution s = new Solution();
int[][] h = {
{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.println(s.pacificAtlantic(h));
System.out.println(s.pacificAtlantic(new int[][]{{1}}));
System.out.println(s.pacificAtlantic(new int[][]{}));
}
}[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
[[0, 0]]
[]Time: O((m * n)^2), a full search from each of the m * n cells. Space: O(m * n).
Optimal: flow backwards from the oceans
Reverse the question: instead of asking where a cell's water goes, ask which cells can send water to an ocean. Start from every cell on the Pacific coast and walk uphill (to neighbors with height >= the current one): everything reached can drain into the Pacific. Do the same from the Atlantic coast. Any cell marked by both searches is an answer. Each search visits each cell at most once, so two searches replace m * n searches.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private boolean[][] climb(int[][] h, List<int[]> starts) {
int m = h.length;
int n = h[0].length;
boolean[][] seen = new boolean[m][n];
Deque<int[]> stack = new ArrayDeque<>();
for (int[] s : starts) {
seen[s[0]][s[1]] = true;
stack.push(s);
}
while (!stack.isEmpty()) {
int[] cell = stack.pop();
int r = cell[0];
int c = cell[1];
for (int[] d : DIRS) {
int nr = r + d[0];
int nc = c + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
continue;
}
if (!seen[nr][nc] && h[nr][nc] >= h[r][c]) {
seen[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
return seen;
}
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> out = new ArrayList<>();
if (heights.length == 0 || heights[0].length == 0) {
return out;
}
int m = heights.length;
int n = heights[0].length;
List<int[]> pacificStarts = new ArrayList<>();
List<int[]> atlanticStarts = new ArrayList<>();
for (int r = 0; r < m; r++) {
pacificStarts.add(new int[]{r, 0});
atlanticStarts.add(new int[]{r, n - 1});
}
for (int c = 0; c < n; c++) {
pacificStarts.add(new int[]{0, c});
atlanticStarts.add(new int[]{m - 1, c});
}
boolean[][] pacific = climb(heights, pacificStarts);
boolean[][] atlantic = climb(heights, atlanticStarts);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (pacific[r][c] && atlantic[r][c]) {
out.add(List.of(r, c));
}
}
}
return out;
}
}
public class Main {
public static void main(String[] args) {
Solution s = new Solution();
int[][] h = {
{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.println(s.pacificAtlantic(h));
System.out.println(s.pacificAtlantic(new int[][]{{1}}));
System.out.println(s.pacificAtlantic(new int[][]{}));
}
}[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
[[0, 0]]
[]Seeding a search with many start cells at once (a multi-source search) is also used in Rotting Oranges and Walls and Gates. Time: O(m * n). Space: O(m * n).