LC 329. Longest Increasing Path in a Matrix

'''
329. Longest Increasing Path in a Matrix

Key Idea: We don't know which coordinate to start at, so we need to try all of them. We can cache the result for each coordinate so we don't need to repeat ourselves. Since the rules say we need to look for INCREASING paths, we don't need to use a visited set for backtracking because a monotonically increasing traversal will never have a cycle. No cycles -> DAG structure, can use memoization.

TC: O(MN)
SC: O(MN)
'''

DIRS = [
    (1, 0), (0, 1), (-1, 0), (0, -1)
]

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        M, N = len(matrix), len(matrix[0])
        cache = [[0] * N for _ in range(M)]
        #visited = set()

        def dfs(row, col) -> int:
            if cache[row][col] > 0:
                return cache[row][col]

            longest_neighbor = 0
            for dy, dx in DIRS:
                new_row = row + dy
                new_col = col + dx
                # if (new_row, new_col) in visited:
                #     continue
                if new_row < 0 or new_row >= M or new_col < 0 or new_col >= N:
                    continue
                if matrix[new_row][new_col] <= matrix[row][col]:
                    continue
                #visited.add((new_row, new_col))
                longest_neighbor = max(longest_neighbor, dfs(new_row, new_col))
                #visited.remove((new_row, new_col))

            cache[row][col] = 1 + longest_neighbor

            return cache[row][col]


        max_len = 0

        for row in range(M):
            for col in range(N):
                max_len = max(max_len, dfs(row, col))

        return max_len