Python beats 98%. DFS template for Matrix
This is a DFS Template to solve matrix questions:\n\npython\ndef dfs(matrix):\n    # 1. Check for an empty graph.\n    if not matrix:\n        return []\n\n    
This is a DFS Template to solve matrix questions:\n\n```python\ndef dfs(matrix):\n    # 1. Check for an empty graph.\n    if not matrix:\n        return []\n\n    # 2. Initialize\n    rows, cols = len(matrix), len(matrix[0])\n    visited = set()\n    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n\n    def traverse(i, j):\n        # a. Check if visited\n        if (i, j) in visited:\n            return\n\t\t# b. Else add to visted\n        visited.add((i, j))\n\n        # c. Traverse neighbors.\n        for direction in directions:\n            next_i, next_j = i + direction[0], j + direction[1]\n            if 0 <= next_i < rows and 0 <= next_j < cols:\n                # d. Add in your question-specific checks.\n                traverse(next_i, next_j)\n\n    # 3. For each point, traverse it.\n    for i in range(rows):\n        for j in range(cols):\n            traverse(i, j)\n\n```\n\nUse this template to addess the problem:\n\n```python\nclass Solution:\n    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n        # Check for an empty graph.\n        if not matrix:\n            return []\n\n        p_visited = set()\n        a_visited = set()\n        rows, cols = len(matrix), len(matrix[0])\n        directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n\n        def traverse(i, j, visited):\n            if (i, j) in visited:\n                return\n            visited.add((i, j))\n            # Traverse neighbors.\n            for direction in directions:\n                next_i, next_j = i + direction[0], j + direction[1]\n                if 0 <= next_i < rows and 0 <= next_j < cols:\n                    # Add in your question-specific checks.\n                    if matrix[next_i][next_j] >= matrix[i][j]:\n                        traverse(next_i, next_j, visited)\n\n        for row in range(rows):\n            traverse(row, 0, p_visited)\n            traverse(row, cols - 1, a_visited)\n\n        for col in range(cols):\n            traverse(0, col, p_visited)\n            traverse(rows - 1, col, a_visited)\n\n        return list(p_visited & a_visited)\n```\n\n> Your runtime beats 98.84 % of python3 submissions\n\n### Complexity Analysis:\n- Time Complexity: since we keep a visited set for each ocean, we only visit a cell if it is not visited before. For each ocean, the worst case is `mn` thus totally `O(mn)`\n\n- Space Complexity: `O(2mn + h) = O(mn)`. \n\t- For each DFS we need `O(h)` space used by the system stack, where `h` is the maximum depth of the recursion. In the worst case, `O(h) = O(m*n)`.\n\t- Each visited set can have at maximum all cells from the matrix so `O(mn)`. Two ocean means `O(2mn)`. \n\n---\n[329. Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/)\n\n**Solution using the above template (LTE):**\n\n```python\nclass Solution:\n    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n        # Check edge case\n        if not matrix:\n            return 0\n\n        # Initialize\n        rows, cols = len(matrix), len(matrix[0])\n        directions = ((0, 1), (0, -1), (-1, 0), (1, 0))\n        visited = set()\n        res = 0\n\n        def dfs(i, j, visited):\n            # Check if visited\n            if (i, j) in visited:\n                return 0\n\t\t\tvisited.add((i, j))\n            res = 1\n\n            # work with neighbors\n            for direction in directions:\n                next_i, next_j = i + direction[0], j + direction[1]\n\n                # for each direction we try to find a new count\n                direction_count = 0\n                if 0 <= next_i < rows and 0 <= next_j < cols:\n                    if matrix[i][j] < matrix[next_i][next_j]:\n                        direction_count = 1 + dfs(next_i, next_j, visited)\n\n                res = max(direction_count, res)\n\n            return res\n\n        for row in range(rows):\n            for col in range(cols):\n                res = max(dfs(row, col, visited), res)\n\n        return res\n```\n\nTime Complexity: `O(mn*mn)`\n\n**Template with Memoization**\n\n```python\nclass Solution:\n    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n        # Check edge case\n        if not matrix:\n            return 0\n\n        # Initialize\n        rows, cols = len(matrix), len(matrix[0])\n        directions = ((0, 1), (0, -1), (-1, 0), (1, 0))\n        memo = [[-1] * cols for _ in range(rows)]\n        res = 0\n\n        def dfs(i, j, visited):\n            # Check if visited\n            if memo[i][j] != -1:\n                return memo[i][j]\n\n            res = 1\n\n            # work with neighbors\n            for direction in directions:\n                next_i, next_j = i + direction[0], j + direction[1]\n\n                # for each direction we try to find a new count\n                direction_count = 0\n                if 0 <= next_i < rows and 0 <= next_j < cols:\n                    if matrix[i][j] < matrix[next_i][next_j]:\n                        direction_count = 1 + dfs(next_i, next_j, visited)\n\n                res = max(direction_count, res)\n\n            memo[i][j] = res\n            return res\n\n        for row in range(rows):\n            for col in range(cols):\n                res = max(dfs(row, col, memo), res)\n\n        return res\n``` \n\n### Complexity Analysis:\n- Time Complexity: `O(mn)` each cell is visited once.\n\n- Space Complexity: `O(mn + h) = O(mn)`. \n\t- For each DFS we need `O(h)` space used by the system stack, where `h` is the maximum depth of the recursion. In the worst case, `O(h) = O(m*n)`.\n\t- Each visited set can have at maximum all cells from the matrix so `O(mn)`\n
[]