Longest Increasing Path in a Matrix

hardAmazon-tagged: Trees & Matrix (mock day)227 stepsJava · Python · C++

Find the longest strictly increasing path moving in 4 directions. The longest path starting at a cell is 1 + the longest from any bigger neighbour. Strict increase means no cycles, so memoise each cell's answer and every cell is solved once.

▶ Watch the animated trace

Traced input: matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]] → 4. Original problem: neetcode.io/problems/longest-increasing-path-in-matrix

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Each cell's answer is computed once.

Key idea

Edges only go from smaller to larger values: the graph is a DAG.
memo[r][c] = longest increasing path starting at (r, c).
A visited set isn't needed; strictness prevents revisiting a cell on the same path.
Topological sort by out-degree (peeling) is the BFS alternative.

Common mistakes

DFS without memoisation is exponential.
Allowing equal neighbours creates cycles.

Solution

Java

int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, best = 0;
    int[][] memo = new int[m][n];
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            best = Math.max(best, longest(matrix, r, c, memo));
    return best;
}

int longest(int[][] g, int r, int c, int[][] memo) {
    if (memo[r][c] != 0) return memo[r][c];
    int best = 1;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nc >= 0 && nr < g.length && nc < g[0].length && g[nr][nc] > g[r][c])
            best = Math.max(best, 1 + longest(g, nr, nc, memo));
    }
    memo[r][c] = best;
    return best;
}

Python

def longestIncreasingPath(matrix: List[List[int]]) -> int:
    m, n = len(matrix), len(matrix[0])
    memo = [[0] * n for _ in range(m)]

    def longest(r: int, c: int) -> int:
        if memo[r][c]: 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 < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + longest(nr, nc))
        memo[r][c] = best
        return best

    return max(longest(r, c) for r in range(m) for c in range(n))

C++

int longest(vector<vector<int>>& g, int r, int c, vector<vector<int>>& memo) {
    if (memo[r][c]) return memo[r][c];
    int best = 1;
    const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (auto& d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nc >= 0 && nr < (int)g.size() && nc < (int)g[0].size() && g[nr][nc] > g[r][c])
            best = max(best, 1 + longest(g, nr, nc, memo));
    }
    memo[r][c] = best;
    return best;
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), best = 0;
    vector<vector<int>> memo(m, vector<int>(n));
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            best = max(best, longest(matrix, r, c, memo));
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single cell A path of one cell.	`matrix = [[1]]`	`1`
All equal No strictly increasing step exists.	`matrix = [[7, 7], [7, 7]]`	`1`
Snake 1 → 2 → 3 → 4 → 5 → 6.	`matrix = [[1, 2, 3], [6, 5, 4]]`	`6`