python DFS detailed intuition and explanation
Intuition\nSome key points:\n1. Water flows downhill or horizontally to cells of equal or lesser height.\n2. We need to find cells that can potentially flow to 
# Intuition\nSome key points:\n1. Water flows downhill or horizontally to cells of equal or lesser height.\n2. We need to find cells that can potentially flow to both the Pacific (top or left boundary) and Atlantic (bottom or right boundary).\n3. We\'ll use DFS to traverse the matrix, focusing on an efficient boundary-based approach.\n\n## Two DFS methods:\n1. DFS from every cell: Inefficient due to redundant checks and dead ends (meaning that cells are unable to reach any ocean)\n2. Performing DFS on boundary cells.\n    - DFS is run \u201Cbackward\u201D from each ocean boundary.\n    - Only valid cells that can lead to either the pacific or atlantic ocean will be reached. This is more efficient because we avoid unnecessary searches on cells that lead to dead ends. This means that there might be some cells in the matrix that never get searched (as they cannot be reached from any of the boundaries)\n\n# Approach\n- Perform DFS from cells along each boundary\n\n- We maintain two visited sets - `pacific_visited` and `atlantic_visited` \u2014 to track cells that can reach the Pacific and Atlantic, respectively.\nThese visited sets do not need to be refreshed on each DFS call because once a cell is added to one of these sets, it means that water can flow from that cell to the corresponding ocean, so we don\'t need to revisit it. \n\n- After DFS completes, the intersection of the 2 sets are taken. To get the output format, we convert each cell in the intersection to a list with list comprehension.\n\n- Do refer to the comments in the code to follow through the implementation!\n\n# Complexity\n- Time complexity:\n$O(m*n)$, `m` = number of rows; `n` = number of columns. \nIn the worse case, we will visit each cell once during DFS and all the cells can reach either ocean. \n\n- Space complexity:\n$2(O(m*n)) = O(m*n)$\nSince we used 2 visited sets, in the worse case, each set could contain all the cells of the matrix (assuming each cell can reach both oceans). \nResults stored in the output list would be $O(m*n)$ in the worse case. \n\n# Code\n```python3 []\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        """\n        dfs on each boundary cell\n        """\n        rows = len(heights)\n        cols = len(heights[0])\n\n        pacific_visited = set()\n        atlantic_visited = set()\n        \n        def dfs(visited, row, col, start_value):\n\n            #check grid boundaries\n            if row < 0 or row >= rows or col < 0 or col >= cols:\n                return\n            \n            #cell has been visited\n            if (row, col) in visited:\n                return\n            \n            #check condition\n            if heights[row][col] < start_value:\n                return\n            \n            visited.add((row, col))\n            \n            #check 4 directions\n            dfs(visited, row+1, col, heights[row][col]) \n            dfs(visited, row-1, col, heights[row][col])\n            dfs(visited, row, col+1, heights[row][col])\n            dfs(visited, row, col-1, heights[row][col])\n            \n        for col in range(cols):\n            dfs(pacific_visited, 0, col, heights[0][col]) #top row\n            dfs(atlantic_visited, rows-1, col, heights[rows-1][col]) #bottom row\n        \n        for row in range(rows):\n            dfs(pacific_visited, row, 0, heights[row][0]) #1st col\n            dfs(atlantic_visited, row, cols-1, heights[row][cols-1]) #bottom row\n        \n        #find the cells that are in both sets\n        output = [list(cell) for cell in pacific_visited & atlantic_visited]\n\n\n        return output\n```\nMuch effort was spent in breaking down this problem, so if this helped you, please do give it an upvote as it means alot to me! Do comment if you have any questions or spot a mistake, thank you :)
['Depth-First Search', 'Matrix', 'Python3']