algoadvance

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can flow from a cell 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.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

Clarifying Questions

1. Direction of Water Flow: Water flows from any cell to its neighboring cells if the neighboring cells have a height less than or equal to the current cell’s height.
2. Boundaries: Specifically, Pacific is connected to the top and left boundaries, and Atlantic is connected to the bottom and right boundaries of the matrix.
3. Output Format: The output should be a list of coordinates [i, j].

Strategy

1. Initialization:
   • Use Depth First Search (DFS) to mark cells reached from both the Pacific and Atlantic oceans.
2. DFS Invocation:
   • Start DFS from all cells on the Pacific edge (top row and left column) and all cells on the Atlantic edge (bottom row and right column).
3. DFS Process:
   • For each cell, check if water can flow to the neighboring cells.
   • Use two matrices (pacific_reachable and atlantic_reachable) to mark cells reachable from each ocean.
4. Result Collection:
   • Collect cells that are reachable from both oceans.

Code

def pacificAtlantic(heights):
    if not heights or not heights[0]:
        return []
    
    m, n = len(heights), len(heights[0])
    
    # Initialize reachable matrices
    pacific_reachable = [[False for _ in range(n)] for _ in range(m)]
    atlantic_reachable = [[False for _ in range(n)] for _ in range(m)]
    
    # Directions for movement: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def dfs(x, y, reachable):
        reachable[x][y] = True
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and not reachable[nx][ny] and heights[nx][ny] >= heights[x][y]:
                dfs(nx, ny, reachable)
    
    # Start DFS from Pacific Ocean boundaries
    for i in range(m):
        dfs(i, 0, pacific_reachable)
        dfs(i, n - 1, atlantic_reachable)
    
    for j in range(n):
        dfs(0, j, pacific_reachable)
        dfs(m - 1, j, atlantic_reachable)
    
    # Collect results
    result = []
    for i in range(m):
        for j in range(n):
            if pacific_reachable[i][j] and atlantic_reachable[i][j]:
                result.append([i, j])
    
    return result

Time Complexity

• Time complexity: (O(m \times n)) where (m) is the number of rows and (n) is the number of columns. Each cell is processed once for both Pacific and Atlantic DFS traversals.
• Space complexity: (O(m \times n)) due to the usage of pacific_reachable and atlantic_reachable matrices and the recursion stack.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?