Longest Increasing Path in a Matrix

1. Problem & Core Objective

Given an m × n matrix, return the length of the longest strictly increasing path. You may move in four directions; you may not move diagonally or wrap around.

matrix = [[9,9,4],          →  4      1 → 2 → 6 → 9
          [6,6,8],
          [2,1,1]]

Constraints: 1 <= m, n <= 200 · 0 <= matrix[i][j] <= 2^31 − 1

What's actually being tested: that memoisation makes a graph search into a DP — and that no visited array is needed, because strict increase makes cycles impossible. That second point is the one people add defensively and shouldn't.

2. First-Principles Thought Process

It's a DAG, not a general graph

Draw an edge from each cell to every strictly larger neighbour. Because values strictly increase along every edge, no cycle can exist — a cycle would require returning to a cell via strictly larger values, which is impossible.

So the graph is a directed acyclic graph, and the longest path in a DAG is computable in linear time. In a general graph, longest path is NP-hard.

That distinction is the whole reason this is tractable.

No visited array is needed

Because cycles can't occur, a DFS from a cell never revisits it within the same path. Adding a visited array is harmless but unnecessary — and worse, it would break the memoisation, since a cell's answer must be reusable across different starting points.

The memo is doing two jobs: caching results, and implicitly preventing re-exploration.

The recurrence

memo[i][j] = the length of the longest increasing path starting at (i, j):

memo[i][j] = 1 + max over strictly larger neighbours of memo[neighbour]

with 1 when no neighbour is larger — the cell alone.

Why the answer is a max over all cells

The longest path can start anywhere, so run the DFS from every cell and take the maximum. Thanks to memoisation, each cell's value is computed once, so the total is O(m·n) regardless of how many starts there are.

Why top-down beats bottom-up here

Tabulating would require processing cells in increasing value order — so you'd sort all m·n cells first, at O(m·n log(m·n)).

Memoised DFS discovers a valid order naturally through the recursion. Same result, no sort. That's unusual: in most DP problems tabulation is the cleaner end state, and here it isn't.

3. Solution Paths

Approach 1 — DFS from every cell without memoisation

public int longestIncreasingPath(int[][] matrix) {
    int best = 0;
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix[0].length; j++)
            best = Math.max(best, dfs(matrix, i, j));
    return best;
}

private int dfs(int[][] m, int i, int j) {
    int best = 1;
    for (int[] d : DIRS) {
        int ni = i + d[0], nj = j + d[1];
        if (ni < 0 || ni >= m.length || nj < 0 || nj >= m[0].length) continue;
        if (m[ni][nj] <= m[i][j]) continue;                  // must strictly increase
        best = Math.max(best, 1 + dfs(m, ni, nj));
    }
    return best;
}

• Time O(2^(m·n)) worst case · Space O(m·n) stack

Counter-questions on this approach

⭐ "Why is there no visited array, and is that safe?"

It's safe, and it's a genuine property rather than an oversight. Every edge goes to a strictly larger value, so following edges strictly increases the value — you can never return to a cell you've left.

The graph is a DAG by construction, so a path can't revisit a node. Adding visited would be harmless for correctness here but would break the memoised version, because a cell's longest path must be reusable from different starting points.

⭐ "Then where does the exponential cost come from?"

Recomputation, not cycles. A cell reachable from many predecessors has its entire subtree re-explored each time.

On a matrix that increases smoothly — say values equal to i + j — the number of paths through a cell grows combinatorially, and each is walked independently.

"How bad at 200 × 200?"

40,000 cells with heavy re-exploration. Not literally 2^40000, but far beyond feasible on adversarial input. The memoised version is 1.6 × 10^5 operations.

Approach 2 — Memoised DFS (optimal)

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] memo = new int[m][n];                    // 0 = not yet computed
    int best = 0;

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            best = Math.max(best, dfs(matrix, i, j, memo));

    return best;
}

private int dfs(int[][] mat, int i, int j, int[][] memo) {
    if (memo[i][j] != 0) return memo[i][j];          // already computed

    int best = 1;                                     // the cell alone
    for (int[] d : DIRS) {
        int ni = i + d[0], nj = j + d[1];
        if (ni < 0 || ni >= mat.length || nj < 0 || nj >= mat[0].length) continue;
        if (mat[ni][nj] <= mat[i][j]) continue;       // strictly increasing only
        best = Math.max(best, 1 + dfs(mat, ni, nj, memo));
    }
    return memo[i][j] = best;
}

Trace — [[9,9,4],[6,6,8],[2,1,1]], starting at (2,1) = 1:

Path 1 → 2 → 6 → 9

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why is memo[i][j] != 0 a safe 'already computed' test?"

Because the answer is always at least 1 — every cell is a path of length 1 on its own. So 0 can never be a legitimate cached value.

That's a domain check, not a convention. In a problem where 0 were a valid answer this sentinel would cause infinite recomputation, and you'd need Integer[][] or a separate flag array. Same discipline as Climbing Stairs and Word Break.

⭐ "Why is the total O(m·n) when the DFS runs from every cell?"

Because each cell's value is computed once. The first DFS that reaches it does the work; every later arrival is an O(1) lookup.

Across the whole run, each cell is expanded once and each of its ≤4 edges examined once — so O(m·n) cells and O(4·m·n) edge checks. The outer double loop contributes m·n calls that mostly return immediately.

That's the same amortisation as flood-fill in Number of Islands: the loop finds work, the memo consumes it.

⭐ "Why does adding a visited array break this?"

Because visited is per-path state, while memo is global. If a cell were marked visited during one DFS and unmarked on the way out, that's just wasted work. But if it stayed marked, later starts would skip it and get wrong answers.

More fundamentally: visited exists to prevent cycles, and there are none. The strict-increase condition already guarantees termination, so the array solves a problem that doesn't exist — and invites confusion about whether the memo is still valid.

"Why not tabulate?"

You could, but it needs cells processed in increasing value order, which means sorting all m·n of them — O(m·n log(m·n)). The memoised DFS finds a valid order through the recursion at no cost.

This is one of the few problems where top-down is genuinely the better end state rather than a stepping stone.

"What about recursion depth?"

The longest possible path is m·n = 40,000 cells, on a matrix where every cell increases — a snake of consecutive values. That's deep enough to overflow Java's default stack.

The fix is the topological-sort version: peel cells with no larger neighbours layer by layer, BFS-style, which is iterative and also O(m·n).

"Values go up to 2^31 − 1. Any overflow concern?"

No — values are only compared, never added. The path length is at most m·n = 40,000, far inside int. Worth confirming, since the stated range looks alarming.

Approach 3 — Topological peeling (iterative)

Compute each cell's out-degree — the count of strictly larger neighbours — then repeatedly peel cells with out-degree 0, decrementing their smaller neighbours. The number of layers is the answer.

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why does the layer count give the longest path?"

Layer 0 is the cells with no larger neighbour — every increasing path ends at one. Layer 1 is cells whose only larger neighbours are in layer 0, and so on.

A cell in layer k has a path of length k + 1 beneath it, so the number of layers is the longest path. It's Kahn's algorithm on the DAG, counting rounds — the same level-counting as Rotting Oranges.

"When would you prefer it?"

When recursion depth is a risk. At 200 × 200 a monotone snake gives 40,000 frames, which can overflow. This version is iterative.

It's more code and less obvious, so I'd write the memoised DFS and mention this as the fix if depth were a concern.

Comparison

4. Why the Optimal Wins

The plain DFS recomputes a cell's entire subtree once per predecessor. One memo line makes each cell's answer computed once and reused, collapsing the total to O(m·n).

The two structural observations are what make it work: the strict-increase condition makes the graph a DAG, so no cycle handling is needed and longest-path is tractable; and the memo doubles as the mechanism that prevents re-exploration.

The framing worth keeping:

Strictly increasing edges make the graph acyclic, so no visited array is needed — and longest path, NP-hard in general, becomes linear. The memo is both the cache and the thing that makes running a DFS from every cell affordable.

5. Java Prerequisites

Memoised grid DFS

if (memo[i][j] != 0) return memo[i][j];       // safe: the answer is always >= 1
...
return memo[i][j] = best;

No visited array — strict increase guarantees acyclicity, and visited would conflict with the memo's reuse across starts.

Direction array — the standard four-neighbour idiom, with bounds checked before indexing.

Sentinel domain check — 0 works because every cell is a path of length ≥ 1.

6. Interview Communication Guide

Clarifying questions: Strictly increasing, or non-decreasing (strictly — non-decreasing would allow cycles and break everything)? Diagonal moves (no)? Can the matrix be 1 × 1 (yes, answer 1)? How large (200 × 200, so recursion depth is a real consideration)?

The pitch

"The key structural observation: draw an edge from each cell to every strictly larger neighbour, and the graph is a DAG — because values strictly increase along every edge, you can never return to a cell you've left.

That matters twice. It means no visited array is needed, which people add defensively and shouldn't — there are no cycles to prevent. And it means longest-path is tractable at all: in a general graph longest path is NP-hard, but in a DAG it's linear.

The recurrence: memo[i][j] is the longest increasing path starting at that cell, which is 1 + max over strictly larger neighbours, or 1 if there are none.

The answer is the max over all cells, since a path can start anywhere. And thanks to memoisation, each cell is computed once — the first DFS that reaches it does the work, and every later arrival is an O(1) lookup. So running a DFS from all 40,000 cells is still O(m·n) overall.

I use 0 as the 'not computed' sentinel, which is safe because the answer is always at least 1 — every cell is a path of length 1 on its own. That's a domain check rather than a convention.

One thing worth noting: this is a rare case where top-down beats bottom-up. Tabulating would need cells in increasing value order, so you'd sort all m·n of them first. The memoised DFS discovers a valid order through the recursion for free.

The one risk is recursion depth — a monotone snake through a 200 × 200 matrix is 40,000 frames, which can overflow. The fix is topological peeling: compute each cell's count of larger neighbours and peel layer by layer, Kahn-style. Iterative, same complexity, and the layer count is the answer."

Edge cases to volunteer:

Name the all-equal matrix. With no strictly larger neighbours anywhere, every cell is its own path and the answer is 1 — a solution using <= instead of < would loop forever, since equal values would create cycles.

7. Follow-Up Questions — Modified Constraints

⭐ "What if paths could be non-decreasing rather than strictly increasing?"

Everything breaks. Equal-valued neighbours create cycles, so the graph is no longer a DAG, the memo becomes unsound, and longest path becomes NP-hard in general.

You'd need to contract equal-valued connected components into single nodes first, then run the DAG algorithm on the condensation. Worth naming as a genuinely different problem.

⭐ "Return the path itself, not its length."

Track which neighbour achieved the maximum at each cell, then walk forward from the best starting cell. O(m·n) extra space, no complexity change.

"Allow diagonal moves."

Eight offsets in DIRS. Still a DAG for the same reason, so nothing structural changes — only more edges.

"What if the matrix were 10^4 × 10^4?"

10^8 cells — the memo alone is 400 MB. Recursion is definitely out; the topological peeling version with an int[] queue of encoded coordinates is the only viable shape, and memory becomes the binding constraint.

"Count the number of longest paths."

Add a count array alongside the memo: when a neighbour ties the current best, add its count; when it beats it, reset. Same traversal, O(m·n). Counts can overflow, so a modulus is usual.

"Find the longest path with at most k decreases allowed."

Add a dimension for the decreases used: memo[i][j][d]. But now cycles become possible within the same d level, so the DAG argument fails and you'd need Bellman-Ford-style bounded rounds. A good illustration of how load-bearing the acyclicity is.