417 Pacific Atlantic Water Flow

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 only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

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

Note: The order of returned grid coordinates does not matter. Both m and n are less than 150. Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

The Idea: I first misinterpretted the problem. It was clarified when I thought about it the following way: imagine there is rain falling onto the grid, which coordinates on grid has their water flow to both the pacific and atlantic counter parts?

In summary, what we do is return the intersection of two depth first searches. We know that inorder for water to travel from both the pacific to atlantic, the dfs must begin along the coast of the respected edges of the grid. It then must 'travel' or traverse where ever it can. So define two dfs, the first along the coast the pacific and the other along the coast to the atlantic. When we travel, we inverse the rule, only go to areas that are higher than it. This works because it is the same thing as making the choice to start from the higher block, and then moving down to the lower block. Then the areas that were visited by both traversals are the solution.

Complexity: O(mn2) time and O(mn2) space

def pacificAtlantic(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[List[int]]
    """

    if not matrix: return []
    rows = len(matrix)
    cols = len(matrix[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited_at = [[False for _ in row] for row in matrix]
    visited_pc = [[False for _ in row] for row in matrix]

    def not_overbound(row, col):
        return 0 <= row < rows and 0 <= col < cols

    def dfs(row, col, visited):
        visited[row][col] = True
        for direction in directions:
            next_r = row + direction[0]
            next_c = col + direction[1]
            if not_overbound(next_r, next_c) and not visited[next_r][next_c] \
                    and matrix[next_r][next_c] >= matrix[row][col]:
                dfs(next_r, next_c, visited)

    for row in range(0, rows):
        dfs(row, 0, visited_pc)         # pacific left
        dfs(row, cols - 1, visited_at)  # atlantic right
    for col in range(0, cols):
        dfs(0, col, visited_pc)         # pacific top
        dfs(rows - 1, col, visited_at)  # atlantic bottom

    both = []
    for row in range(0, rows):
        for col in range(0, cols):
            if visited_at[row][col] and visited_pc[row][col]:
                both.append([row, col])
    return both