text: # Time:  O(m * n)
  # Space: O(m * n)
  
  # 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).
  
  class Solution(object):
      def pacificAtlantic(self, matrix):
          """
          :type matrix: List[List[int]]
          :rtype: List[List[int]]
          """
          PACIFIC, ATLANTIC = 1, 2
  
          def pacificAtlanticHelper(matrix, x, y, prev_height, prev_val, visited, res):
              if (not 0 <= x < len(matrix)) or \
                 (not 0 <= y < len(matrix[0])) or \
                 matrix[x][y] < prev_height or \
                 (visited[x][y] | prev_val) == visited[x][y]:
                  return
  
              visited[x][y] |= prev_val 
              if visited[x][y] == (PACIFIC | ATLANTIC):
                  res.append((x, y))
      
              for d in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
                  pacificAtlanticHelper(matrix, x + d[0], y + d[1], matrix[x][y], visited[x][y], visited, res)
          
          if not matrix:
              return []
  
          res = []
          m, n = len(matrix),len(matrix[0])
          visited = [[0 for _ in xrange(n)] for _ in xrange(m)]
  
          for i in xrange(m):
              pacificAtlanticHelper(matrix, i, 0, float("-inf"), PACIFIC, visited, res)
              pacificAtlanticHelper(matrix, i, n - 1, float("-inf"), ATLANTIC, visited, res)
          for j in xrange(n):
              pacificAtlanticHelper(matrix, 0, j, float("-inf"), PACIFIC, visited, res)
              pacificAtlanticHelper(matrix, m - 1, j, float("-inf"), ATLANTIC, visited, res)
  
          return res
  