417. Pacific Atlantic Water Flow

Given an m × 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:

1. The order of returned grid coordinates does not matter.
2. 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).

Solution: DFS

UP = (-1, 0)
DOWN = (1, 0)
LEFT = (0, -1)
RIGHT = (0, 1)


class Solution(object):
    def pacificAtlantic(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        if not matrix:
            return []

        result = []
        rows = len(matrix)
        cols = len(matrix[0])
        visited = [[0] * cols for _ in xrange(rows)]

        def neighbors(row, col):
            for x, y in UP, DOWN, LEFT, RIGHT:
                i = row + x
                j = col + y
                if 0 <= i < rows and 0 <= j < cols:
                    yield i, j

        def dfs(row, col, state):
            # visited by current dfs
            if visited[row][col] == state:
                return

            # visited by previous dfs
            if visited[row][col]:
                result.append([row, col])

            visited[row][col] = state
            for i, j in neighbors(row, col):
                if matrix[i][j] >= matrix[row][col]:
                    dfs(i, j, state)

        # up border
        for col in xrange(cols):
            dfs(0, col, 1)

        # left border
        for row in xrange(1, rows):
            dfs(row, 0, 1)

        # down border
        for col in xrange(cols):
            dfs(rows - 1, col, 2)

        # right border
        for row in xrange(rows - 1):
            dfs(row, cols - 1, 2)

        return result

Lessons:

• Reverse the water flow!
• Start with up and left borders, DFS to visit all higher cells.
• Then start with the down and right borders, DFS to visit all higher cells. If a cell was already visited in previous DFS, we found a valid peak!