# DFS solution

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:

        n, m = len(heights), len(heights[0])
        result = []
        p_visited = set()
        a_visited = set()

        def dfs(r, c, visited):
            if r not in range(n) or c not in range(m) or (r, c) in visited:
                return

            visited.add((r, c))
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            for (dr, dc) in directions:
                row = r + dr
                col = c + dc

                if row in range(n) and col in range(m) and heights[r][c] <= heights[row][col]:
                    dfs(row, col, visited)

        for i in range(n):
            dfs(i, 0, p_visited)
            dfs(i, m-1, a_visited)

        for j in range(m):
            dfs(0, j, p_visited)
            dfs(n-1, j, a_visited)

        for r in range(n):
            for c in range(m):
                if (r, c) in p_visited and (r, c) in a_visited:
                    result.append([r, c])

        return result