Pacific Atlantic Water Flow medium

Problem Statement

You are given an m x n integer matrix heights representing the height of each unit cell in a continent. The Pacific ocean touches the left and top edges of the continent, and the Atlantic ocean touches the right and bottom edges.

Water can only flow in four directions: up, down, left, and right. Water flows from a cell to an adjacent cell only if the height of the adjacent cell is not higher than the height of the current cell.

Find the cells from which water can flow to both the Pacific and Atlantic oceans. Return a list of coordinates [row, col] of these cells. You may return the answer in any order.

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 = [[2,1],[1,2]] Output: [[0,0],[0,1],[1,0],[1,1]]

Steps

1. Initialization: Create two boolean matrices, pacific and atlantic, of the same size as heights. Initialize all elements to False. These matrices will track which cells can reach the Pacific and Atlantic oceans, respectively.

2. Breadth-First Search (BFS): Perform BFS from the boundary cells touching the Pacific Ocean (top and left edges) and mark all reachable cells in the pacific matrix as True. Similarly, perform BFS from the boundary cells touching the Atlantic Ocean (bottom and right edges) and mark all reachable cells in the atlantic matrix as True.

3. Identify Common Cells: Iterate through the heights matrix. For each cell, if both pacific[row][col] and atlantic[row][col] are True, it means water can flow to both oceans from that cell. Add the coordinates [row, col] to the result list.

4. Return Result: Return the list of coordinates.

Explanation

The BFS algorithm efficiently explores all reachable cells from a starting point. By performing BFS from both ocean boundaries, we find all cells that can reach each ocean. Then, comparing the two boolean matrices allows us to identify cells that can reach both.

Code

from collections import deque

def pacificAtlantic(heights):
    """
    Finds cells from which water can flow to both the Pacific and Atlantic oceans.

    Args:
        heights: A list of lists representing the height of each cell.

    Returns:
        A list of coordinates [row, col] of cells that can flow to both oceans.
    """

    rows, cols = len(heights), len(heights[0])
    pacific = [[False] * cols for _ in range(rows)]
    atlantic = [[False] * cols for _ in range(rows)]
    
    def bfs(ocean, visited):
        q = deque()
        for r in range(rows):
            if ocean == 'pacific':
                q.append((r,0))
                visited[r][0] = True
            if ocean == 'atlantic':
                q.append((r,cols-1))
                visited[r][cols-1] = True
        for c in range(cols):
            if ocean == 'pacific':
                q.append((0,c))
                visited[0][c] = True
            if ocean == 'atlantic':
                q.append((rows-1,c))
                visited[rows-1][c] = True

        while q:
            r,c = q.popleft()
            for dr,dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr,nc = r+dr,c+dc
                if 0<=nr<rows and 0<=nc<cols and not visited[nr][nc] and heights[nr][nc] >= heights[r][c]:
                    visited[nr][nc] = True
                    q.append((nr,nc))

    bfs('pacific', pacific)
    bfs('atlantic', atlantic)

    result = []
    for r in range(rows):
        for c in range(cols):
            if pacific[r][c] and atlantic[r][c]:
                result.append([r, c])
    return result

Complexity

• Time Complexity: O(m * n), where m and n are the dimensions of the matrix. This is dominated by the BFS traversals.
• Space Complexity: O(m * n), due to the creation of the pacific and atlantic matrices and the queue used in BFS. In the worst case the queue could hold all the cells.