Editorial: Longest Increasing Path in a Matrix

by admin · Oct. 18, 2026

1 Intuition

Strictly increasing moves can never cycle, so the grid is a DAG.

2 Approach

DFS from every cell with memoization: the longest path from a cell is 1 + the best path from any larger neighbour.

3 Complexity Analysis

Time O(rows·cols), Space O(rows·cols).

4 Solution Code

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        memo = {}
        def dfs(r, c):
            if (r, c) in memo:
                return memo[(r, c)]
            best = 1
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            memo[(r, c)] = best
            return best
        return max(dfs(r, c) for r in range(rows) for c in range(cols))

5 Code Walkthrough

The reference solution below implements the approach step by step.