Skip to main content

Pacific Atlantic Water Flow

Question​

Given a matrix of size m x n, determine which cells are located on the Pacific and Atlantic edges of the matrix, and which cells are able to reach both edges of the matrix.

Example 1
Input:
matrix = 
[
 [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]]

Solution​

all//Pacific Atlantic Water Flow.py


def pacificAtlantic(matrix):
    if not matrix:
        return []
    m, n = len(matrix), len(matrix[0])
    p_visited = [[False for _ in range(n)] for _ in range(m)]
    a_visited = [[False for _ in range(n)] for _ in range(m)]
    result = []

    def dfs(i, j, visited):
        visited[i][j] = True
        for (x, y) in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if 0<=x<m and 0<=y<n and not visited[x][y] and matrix[x][y]>=matrix[i][j]:
                dfs(x,y,visited)

    for i in range(m):
        dfs(i, 0, p_visited)
        dfs(i, n-1, a_visited)
    for j in range(n):
        dfs(0, j, p_visited)
        dfs(m-1, j, a_visited)
    for i in range(m):
        for j in range(n):
            if p_visited[i][j] and a_visited[i][j]:
                result.append([i, j])
    return result