Longest Increasing Path in a Matrix

Free with account Updated Nov 19, 2026 · 7 min read
On this page

    Problem statement

    Given an R × C grid of integers, return the length of the longest path in which each step moves up, down, left or right to a strictly larger value. The length counts cells. Diagonal moves and wrapping around the edges are not allowed; the path may start anywhere.

    A grid search that looks like it needs backtracking, but doesn't: because every step goes strictly uphill, a path can never come back to a cell, so each cell's answer can be computed once and reused. That makes it a DP on a directed acyclic graph, solvable by memoised DFS or by topological sort. Original problem: LeetCode 329.

    Example

    Starting at the 1 in the centre, the path spirals out through every cell in increasing order: length 9.
    Starting at the 1 in the centre, the path spirals out through every cell in increasing order: length 9.
    Input:  [[3, 4, 5],
             [2, 1, 6],
             [9, 8, 7]]
    Output: 9          # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
    Input:  [[7, 7],
             [7, 7]]
    Output: 1          # equal values don't count as increasing

    Constraints (assumed)

    • 1 ≤ R, C ≤ 200.
    • 0 ≤ grid[r][c] ≤ 2³¹ − 1.

    What this question tests

    • Noticing that "strictly increasing" makes the move graph acyclic, so no visited set is needed.
    • Memoised DFS (top-down DP) over grid cells.
    • The equivalent topological sort view: peel the grid layer by layer from the local maxima.

    Questions to ask first

    1. Strictly increasing, or non-decreasing? Equal neighbours would create cycles and change the problem. (Here: strictly.)
    2. Four directions or eight? (Here: four.)
    3. Length in cells or in moves? (Here: cells, so a single cell has length 1.)
    4. Do you need the path or only its length? (Here: the length.)