#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/graphs-dfs/longest-increasing-path-in-a-matrix-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/graphs-dfs/longest-increasing-path-in-a-matrix-implementation

Repovive

LeetCode 329 Longest Increasing Path in a Matrix - Implementation - Graphs - DFS | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 329 Longest Increasing Path in a Matrix - Implementation

The approach

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.