• Time:O(mn)
• Space:O(mn)

## C++

``````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;
}
};
``````

## JAVA

``````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])

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;
}
}
}
}
``````

## Python

``````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]]
``````

• Time:O(mn)
• Space:O(mn)

## C++

``````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]);
}
};
``````

## JAVA

``````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])

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);
}
}
``````

## Python

``````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]]
``````