Problem Statement

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rainwater can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rainwater can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Additional information

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 10^5

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2:

Input: heights = [[1]]

Output: [[0,0]]

Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans, as it touches both oceans.

Brute Force (DFS from Every Cell)

Intuition

A naive way to solve this is to simulate the exact physical process the problem describes. For every single cell on the board, we can release a drop of water and use a Depth-First Search (DFS) to see everywhere it can flow.

The water can only step to a neighboring cell if that neighbor has a height less than or equal to the current cell. During the DFS, if the water ever touches the top or left boundary, we mark that the Pacific is reachable. If it touches the bottom or right boundary, we mark that the Atlantic is reachable. If both become true, we add the starting cell to our results.

Algorithm

1. If heights is empty, return an empty list.
2. Iterate through every row r and column c in the grid.
3. For each cell, initialize a visited set and run a recursive dfs(r, c, visited) function.
4. Inside dfs:

• Check if the current coordinates touch the Pacific (r == 0 or c == 0) or the Atlantic (r == rows - 1 or c == cols - 1).
• Add (r, c) to visited.
• Look at all 4 neighbors. If a neighbor is within bounds, not visited, and its height is <= heights[r][c], recursively call dfs on it.
• Return whether the Pacific and Atlantic were reached.

5. If a starting cell successfully reaches both, append [r, c] to the result list.

def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
    if not heights or not heights[0]:
        return []
        
    rows, cols = len(heights), len(heights[0])
    res = []
    
    def dfs(r, c, visited):
        pacific = (r == 0 or c == 0)
        atlantic = (r == rows - 1 or c == cols - 1)
        
        visited.add((r, c))
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                if heights[nr][nc] <= heights[r][c]:
                    p_reach, a_reach = dfs(nr, nc, visited)
                    pacific = pacific or p_reach
                    atlantic = atlantic or a_reach
                    
        return [pacific, atlantic]

    for r in range(rows):
        for c in range(cols):
            visited = set()
            p, a = dfs(r, c, visited)
            if p and a:
                res.append([r, c])
                
    return res

Time & Space Complexity

• Time complexity: O((M * N)^2)

• Reason: M is the number of rows and N is the number of columns. For every single cell (M * N), we run a full DFS which could potentially visit every other cell on the board in the worst case (M * N). Multiplying these gives O((M * N)^2).

• Space complexity: O(M * N)

• Reason: The visited set and the recursion stack can grow up to the size of the entire grid.

Reverse DFS from Oceans - Optimal

Intuition

Instead of dropping water on every cell and seeing where it goes, we can completely reverse our perspective! What if we start from the oceans and let the water flow uphill?

We know the exact cells that touch the Pacific (the top and left edges) and the Atlantic (the bottom and right edges). If we start a DFS from these edge cells and only allow the water to move to neighbors that are greater than or equal to the current height, we can easily map out all cells capable of reaching that ocean.

By maintaining two separate sets (pacific_reachable and atlantic_reachable), we can map the entire grid in just two passes. The final answer is simply the intersection of these two sets!

Algorithm

1. Create two empty sets: pacific and atlantic.
2. Define a recursive helper dfs(r, c, visited, prev_height).
3. Base Cases for DFS: If r or c is out of bounds, if (r, c) is already in visited, or if heights[r][c] < prev_height (water can't flow uphill), return immediately.
4. Add (r, c) to visited.
5. Call dfs on all 4 neighbors, passing heights[r][c] as the new prev_height.
6. Pacific Pass: Loop through the first row and first column, calling dfs and populating the pacific set.
7. Atlantic Pass: Loop through the last row and last column, calling dfs and populating the atlantic set.
8. Loop through every cell in the grid. If a cell exists in both the pacific and atlantic sets, append its coordinates to the result list.

def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
    if not heights or not heights[0]:
        return []
        
    rows, cols = len(heights), len(heights[0])
    pacific = set()
    atlantic = set()
    
    def dfs(r, c, visited, prev_height):
        if (r < 0 or c < 0 or r >= rows or c >= cols or 
            (r, c) in visited or heights[r][c] < prev_height):
            return
            
        visited.add((r, c))
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
        for dr, dc in directions:
            dfs(r + dr, c + dc, visited, heights[r][c])
            
    # Run DFS from the first row (Pacific) and last row (Atlantic)
    for c in range(cols):
        dfs(0, c, pacific, heights[0][c])
        dfs(rows - 1, c, atlantic, heights[rows - 1][c])
        
    # Run DFS from the first col (Pacific) and last col (Atlantic)
    for r in range(rows):
        dfs(r, 0, pacific, heights[r][0])
        dfs(r, cols - 1, atlantic, heights[r][cols - 1])
        
    res = []
    # Find the intersection of both sets
    for r in range(rows):
        for c in range(cols):
            if (r, c) in pacific and (r, c) in atlantic:
                res.append([r, c])
                
    return res

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: Every cell is visited at most twice (once during the Pacific pass, once during the Atlantic pass). The condition (r, c) in visited prevents duplicate work.

• Space complexity: O(M * N)

• Reason: The two hash sets (pacific and atlantic) and the recursion stack can each hold up to M * N elements in the worst case.