Cover image for LeetCode Daily Problem P417: Pacific Atlantic Water Flow

LeetCode Daily Problem P417: Pacific Atlantic Water Flow

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-10-05

init

Multi-source BFS

Problem:

P417 Pacific Atlantic Water Flow

https://leetcode.cn/problems/pacific-atlantic-water-flow/description/?envType=daily-question&envId=2025-10-05

Multi-source BFSIt is to start BFS from multiple sources simultaneously. The key idea is to put multiple ‘source points’ into the queue as the initial layer (layer 0), and then expand them outward simultaneously in one BFS. This is equivalent to all sources ‘diffusing waves’ together, and the layer number when a node is first visited is the shortest distance to the nearest source.

If we use ordinary BFS for this problem, we would have to do BFS for each vertex. Therefore, using multi-source BFS is better. That is, if a cell can flow to an ocean (Pacific or Atlantic), then its higher neighbor must also be able to flow to the ocean that the cell can reach.
During initialization, enqueue all points on the island’s coast, i.e., all cells on the boundary. Each time a cell is dequeued, if a neighbor has a height higher than this cell, then the ocean that this cell can reach, that neighbor can also reach.
The key issue is how to handle duplicates. Each cell has two states. Only when these two states are fixed and determined not to change, the processing is complete. Therefore, if during the processing of four neighbors, a neighbor’s state does not change, do not enqueue it; enqueue only the neighbors whose states have changed.

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <queue>
#include <utility>
#include <vector>

using std::pair;
using std::queue;
using std::vector;

class Solution {
public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
    int m = heights.size(), n = heights[0].size();
    int i, j, k;
    int neighbor_i, neighbor_j;
    // (i-1, j) (i,j+1) (i+1,j)  (i,j-1)
    int arr[] = {-1, 0, 1, 0, -1};
    queue<pair<int, int>> que;
    vector<vector<pair<int, int>>> vec(m, vector<pair<int, int>>(n, {-1, -1}));
    bool updated = false;
    vector<vector<int>> result;

    // First row and last row
    for (int j = 0; j < n; j++) {
      vec[0][j].first = 1;
      vec[m - 1][j].second = 1;
      que.push({0, j});
      que.push({m - 1, j});
    }
    // First column and last column
    for (int i = 0; i < m; i++) {
      vec[i][0].first = 1;
      vec[i][n - 1].second = 1;
      que.push({i, 0});
      que.push({i, n - 1});
    }

    while (!que.empty()) {
      i = que.front().first;
      j = que.front().second;

      que.pop();
      // If it can reach Ocean, then its higher neighbors can also reach it.
      for (k = 0; k <= 3; k++) {
        neighbor_i = i + arr[k];
        neighbor_j = j + arr[k + 1];
        updated = false;
        if ((neighbor_i >= 0 && neighbor_i < m && neighbor_j >= 0 &&
             neighbor_j < n) &&
            heights[neighbor_i][neighbor_j] >= heights[i][j]) {

          if (vec[i][j].first == 1 && vec[neighbor_i][neighbor_j].first != 1) {
            vec[neighbor_i][neighbor_j].first = 1;
            updated = true;
          }
          if (vec[i][j].second == 1 &&
              vec[neighbor_i][neighbor_j].second != 1) {
            vec[neighbor_i][neighbor_j].second = 1;
            updated = true;
          }

          // Neighbors join the queue only when the neighbor's state is changed.
          if (updated) {
            que.push({neighbor_i, neighbor_j});
          }
        }
      }
    }

    for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++) {
        if (vec[i][j].first == 1 && vec[i][j].second == 1) {
          result.push_back({i, j});
        }
      }
    }

    return result;
  }
};