LeetCode 329 Longest Increasing Path in a Matrix - Implementation

DFS with memoization.

function longestIncreasingPath(matrix): m, n = len(matrix), len(matrix[0]) dp = [[0] * n for _ in range(m)]

def dfs(r, c):
    if dp[r][c]:
        return dp[r][c]
    val = matrix[r][c]
    dp[r][c] = 1
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > val:
            dp[r][c] = max(dp[r][c], 1 + dfs(nr, nc))
    return dp[r][c]

return max(dfs(i, j) for i in range(m) for j in range(n))

$O(m \cdot n)$ time and space.