Solutions

# Start from the boarders and explore (DFS inwards) to find all cells that can reach the Atlantic. Do the same with the Pacific. Then find the intersection of the two sets of cells.
# graphs

# DFS - O(M*N) time, O(M*N) space
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    ROWS, COLS = len(heights), len(heights[0])
    pacific = set()
    atlantic = set()

    def dfs(r: int, c: int, prev: int, visited: set):
        if r<0 or r>=ROWS or c<0 or c>=COLS or \
            heights[r][c] < prev or (r,c) in visited:
            return

        val = heights[r][c]
        visited.add((r,c))
        dfs(r+1, c, val, visited)
        dfs(r-1, c, val, visited)
        dfs(r, c+1, val, visited)
        dfs(r, c-1, val, visited)
    
    # Add borders as part of the DFS (as first cells visited)
    for c in range(COLS):
        dfs(0, c, heights[0][c], pacific)
        dfs(ROWS-1, c, heights[ROWS-1][c], atlantic)

    for r in range(ROWS):
        dfs(r, 0, heights[r][0], pacific)
        dfs(r, COLS-1, heights[r][COLS-1], atlantic)

    return list(pacific & atlantic)


# BFS - O(M*N) time, O(M*N) space
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    ROWS, COLS = len(heights), len(heights[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    pac = [[False] * COLS for _ in range(ROWS)]
    atl = [[False] * COLS for _ in range(ROWS)]

    from collections import deque

    def bfs(source, ocean):
        q = deque(source)
        while q:
            r, c = q.popleft()
            ocean[r][c] = True
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < ROWS and 0 <= nc < COLS and
                    not ocean[nr][nc] and
                    heights[nr][nc] >= heights[r][c]
                ):
                    q.append((nr, nc))

    pacific = []
    atlantic = []
    for c in range(COLS):
        pacific.append((0, c))
        atlantic.append((ROWS - 1, c))

    for r in range(ROWS):
        pacific.append((r, 0))
        atlantic.append((r, COLS - 1))

    bfs(pacific, pac)
    bfs(atlantic, atl)

    res = []
    for r in range(ROWS):
        for c in range(COLS):
            if pac[r][c] and atl[r][c]:
                res.append([r, c])
    return res


# Brute force - O(M*N*4^(M*N)) time, O(M*N) space
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    ROWS, COLS = len(heights), len(heights[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    pacific = atlantic = False

    def dfs(r, c, prevVal):
        nonlocal pacific, atlantic
        if r < 0 or c < 0:
            pacific = True
            return
        if r >= ROWS or c >= COLS:
            atlantic = True
            return
        if heights[r][c] > prevVal:
            return

        tmp = heights[r][c]
        heights[r][c] = float('inf')
        for dx, dy in directions:
            dfs(r + dx, c + dy, tmp)
            if pacific and atlantic:
                break
        heights[r][c] = tmp

    res = []
    for r in range(ROWS):
        for c in range(COLS):
            pacific = False
            atlantic = False
            dfs(r, c, float('inf'))
            if pacific and atlantic:
                res.append([r, c])
    return res