Longest Increasing Path in a Matrix

Intuition

Because every move must go to a strictly larger value, no path can ever revisit a cell, so the grid behaves like a directed acyclic graph. The longest increasing path that starts at a cell depends only on the longest increasing paths starting at its larger neighbors, which makes the problem a natural fit for recursion. Once we compute the best length for a cell we never need to recompute it, so a memo table turns an exponential search into linear work. The overall answer is the maximum starting length taken over every cell in the grid.

Algorithm walkthrough

1. 1Create a memo grid the same size as the matrix, initialized to zero to mark cells whose answer is not yet known.
2. 2Define a recursive function that, for a given cell, returns the length of the longest increasing path beginning there.
3. 3Inside the recursion look at the four neighbors; whenever a neighbor holds a strictly larger value, recurse into it and consider one plus that result.
4. 4Take the best value among all valid neighbors (at least one for the cell itself), store it in the memo, and return it.
5. 5Call the function for every cell and return the largest value produced.

Implementation

from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        memo = [[0] * cols for _ in range(rows)]
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> int:
            if memo[r][c]:
                return memo[r][c]
            best = 1
            for dr, dc in directions:
                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))