Skip to content

417. Pacific Atlantic Water Flow 👍

Approach 1: BFS

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
 public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = heights.size();
    const int n = heights[0].size();
    vector<vector<int>> ans;
    queue<pair<int, int>> qP;
    queue<pair<int, int>> qA;
    vector<vector<bool>> seenP(m, vector<bool>(n));
    vector<vector<bool>> seenA(m, vector<bool>(n));

    auto bfs = [&](queue<pair<int, int>>& q, vector<vector<bool>>& seen) {
      while (!q.empty()) {
        const auto [i, j] = q.front();
        q.pop();
        const int h = heights[i][j];
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (seen[x][y] || heights[x][y] < h)
            continue;
          q.emplace(x, y);
          seen[x][y] = true;
        }
      }
    };

    for (int i = 0; i < m; ++i) {
      qP.emplace(i, 0);
      qA.emplace(i, n - 1);
      seenP[i][0] = true;
      seenA[i][n - 1] = true;
    }

    for (int j = 0; j < n; ++j) {
      qP.emplace(0, j);
      qA.emplace(m - 1, j);
      seenP[0][j] = true;
      seenA[m - 1][j] = true;
    }

    bfs(qP, seenP);
    bfs(qA, seenA);

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (seenP[i][j] && seenA[i][j])
          ans.push_back({i, j});

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
  public List<List<Integer>> pacificAtlantic(int[][] heights) {
    final int m = heights.length;
    final int n = heights[0].length;
    List<List<Integer>> ans = new ArrayList<>();
    Queue<Pair<Integer, Integer>> qP = new ArrayDeque<>();
    Queue<Pair<Integer, Integer>> qA = new ArrayDeque<>();
    boolean[][] seenP = new boolean[m][n];
    boolean[][] seenA = new boolean[m][n];

    for (int i = 0; i < m; ++i) {
      qP.offer(new Pair<>(i, 0));
      qA.offer(new Pair<>(i, n - 1));
      seenP[i][0] = true;
      seenA[i][n - 1] = true;
    }

    for (int j = 0; j < n; ++j) {
      qP.offer(new Pair<>(0, j));
      qA.offer(new Pair<>(m - 1, j));
      seenP[0][j] = true;
      seenA[m - 1][j] = true;
    }

    bfs(heights, qP, seenP);
    bfs(heights, qA, seenA);

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (seenP[i][j] && seenA[i][j])
          ans.add(new ArrayList<>(List.of(i, j)));

    return ans;
  }

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  private void bfs(int[][] heights, Queue<Pair<Integer, Integer>> q, boolean[][] seen) {
    while (!q.isEmpty()) {
      final int i = q.peek().getKey();
      final int j = q.poll().getValue();
      final int h = heights[i][j];
      for (int[] dir : dirs) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (x < 0 || x == heights.length || y < 0 || y == heights[0].length)
          continue;
        if (seen[x][y] || heights[x][y] < h)
          continue;
        q.offer(new Pair<>(x, y));
        seen[x][y] = true;
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
  def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(heights)
    n = len(heights[0])
    qP = collections.deque()
    qA = collections.deque()
    seenP = [[False] * n for _ in range(m)]
    seenA = [[False] * n for _ in range(m)]

    for i in range(m):
      qP.append((i, 0))
      qA.append((i, n - 1))
      seenP[i][0] = True
      seenA[i][n - 1] = True

    for j in range(n):
      qP.append((0, j))
      qA.append((m - 1, j))
      seenP[0][j] = True
      seenA[m - 1][j] = True

    def bfs(q: deque, seen: list[list[bool]]):
      while q:
        i, j = q.popleft()
        h = heights[i][j]
        for dx, dy in dirs:
          x = i + dx
          y = j + dy
          if x < 0 or x == m or y < 0 or y == n:
            continue
          if seen[x][y] or heights[x][y] < h:
            continue
          q.append((x, y))
          seen[x][y] = True

    bfs(qP, seenP)
    bfs(qA, seenA)

    return [[i, j] for i in range(m) for j in range(n) if seenP[i][j] and seenA[i][j]]

Approach 2: DFS

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    const int m = heights.size();
    const int n = heights[0].size();
    vector<vector<int>> ans;
    vector<vector<bool>> seenP(m, vector<bool>(n));
    vector<vector<bool>> seenA(m, vector<bool>(n));

    for (int i = 0; i < m; ++i) {
      dfs(heights, i, 0, seenP);
      dfs(heights, i, n - 1, seenA);
    }

    for (int j = 0; j < n; ++j) {
      dfs(heights, 0, j, seenP);
      dfs(heights, m - 1, j, seenA);
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (seenP[i][j] && seenA[i][j])
          ans.push_back({i, j});

    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& heights, int i, int j,
           vector<vector<bool>>& seen, int h = 0) {
    if (i < 0 || i == heights.size() || j < 0 || j == heights[0].size())
      return;
    if (seen[i][j] || heights[i][j] < h)
      return;

    seen[i][j] = true;
    dfs(heights, i + 1, j, seen, heights[i][j]);
    dfs(heights, i - 1, j, seen, heights[i][j]);
    dfs(heights, i, j + 1, seen, heights[i][j]);
    dfs(heights, i, j - 1, seen, heights[i][j]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public List<List<Integer>> pacificAtlantic(int[][] heights) {
    final int m = heights.length;
    final int n = heights[0].length;
    List<List<Integer>> ans = new ArrayList<>();
    boolean[][] seenP = new boolean[m][n];
    boolean[][] seenA = new boolean[m][n];

    for (int i = 0; i < m; ++i) {
      dfs(heights, i, 0, 0, seenP);
      dfs(heights, i, n - 1, 0, seenA);
    }

    for (int j = 0; j < n; ++j) {
      dfs(heights, 0, j, 0, seenP);
      dfs(heights, m - 1, j, 0, seenA);
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (seenP[i][j] && seenA[i][j])
          ans.add(new ArrayList<>(List.of(i, j)));

    return ans;
  }

  private void dfs(final int[][] heights, int i, int j, int h, boolean[][] seen) {
    if (i < 0 || i == heights.length || j < 0 || j == heights[0].length)
      return;
    if (seen[i][j] || heights[i][j] < h)
      return;

    seen[i][j] = true;
    dfs(heights, i + 1, j, heights[i][j], seen);
    dfs(heights, i - 1, j, heights[i][j], seen);
    dfs(heights, i, j + 1, heights[i][j], seen);
    dfs(heights, i, j - 1, heights[i][j], seen);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
  def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
    m = len(heights)
    n = len(heights[0])
    seenP = [[False] * n for _ in range(m)]
    seenA = [[False] * n for _ in range(m)]

    def dfs(i: int, j: int, h: int, seen: list[list[bool]]) -> None:
      if i < 0 or i == m or j < 0 or j == n:
        return
      if seen[i][j] or heights[i][j] < h:
        return

      seen[i][j] = True
      dfs(i + 1, j, heights[i][j], seen)
      dfs(i - 1, j, heights[i][j], seen)
      dfs(i, j + 1, heights[i][j], seen)
      dfs(i, j - 1, heights[i][j], seen)

    for i in range(m):
      dfs(i, 0, 0, seenP)
      dfs(i, n - 1, 0, seenA)

    for j in range(n):
      dfs(0, j, 0, seenP)
      dfs(m - 1, j, 0, seenA)

    return [[i, j]
            for i in range(m)
            for j in range(n)
            if seenP[i][j] and seenA[i][j]]