LeetCode Solutions

			

class Solution {
 public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    const int m = heights.size();
    const int n = heights[0].size();
    const vector<int> dirs{0, 1, 0, -1, 0};
    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 (int k = 0; k < 4; ++k) {
          const int x = i + dirs[k];
          const int y = j + dirs[k + 1];
          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;
  }
};

			

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<int[]> qP = new ArrayDeque<>();
    Queue<int[]> 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 int[] {i, 0});
      qA.offer(new int[] {i, n - 1});
      seenP[i][0] = true;
      seenA[i][n - 1] = true;
    }

    for (int j = 0; j < n; ++j) {
      qP.offer(new int[] {0, j});
      qA.offer(new int[] {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<>(Arrays.asList(i, j)));

    return ans;
  }

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

  private void bfs(int[][] heights, Queue<int[]> q, boolean[][] seen) {
    while (!q.isEmpty()) {
      final int i = q.peek()[0];
      final int j = q.poll()[1];
      final int h = heights[i][j];
      for (int k = 0; k < 4; ++k) {
        final int x = i + dirs[k];
        final int y = j + dirs[k + 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 int[] {x, y});
        seen[x][y] = true;
      }
    }
  }
}

			

class Solution:
  def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    m = len(heights)
    n = len(heights[0])
    dirs = [0, 1, 0, -1, 0]
    qP = deque()
    qA = 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 k in range(4):
          x = i + dirs[k]
          y = j + dirs[k + 1]
          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]]