Longest Increasing Path in a Matrix

Problem Statement

Given an m x n matrix of integers, find the length of the longest strictly increasing path. From any cell, you can move in four directions: up, down, left, or right. Diagonal movement is not allowed. Each step must move to a cell with a strictly greater value.

Consider this matrix:

9 9 4
6 6 8
2 1 1

The longest increasing path is 1 → 2 → 6 → 9, yielding a length of 4. The path starts at cell (2,1) with value 1, moves to (2,0) with value 2, then to (1,0) with value 6, and finally to (0,0) with value 9.

A naive first instinct is to try every possible path from every cell. That approach works, but it collapses under real-world matrix sizes. The trick is recognizing how the strict-increase constraint shapes the problem into something far more tractable.

Key Insight: The Matrix is a DAG

The strict-increase constraint eliminates cycles entirely. If you move from cell A to cell B, then value(A) < value(B). You can never return to A, because that would require a value smaller than B, then smaller than A — contradicting the fact that value(A) < value(B). No cycles means the matrix, viewed as a graph, forms a Directed Acyclic Graph (DAG).

Each cell becomes a node. A directed edge connects cell (i, j) to neighbor (ni, nj) whenever matrix[ni][nj] > matrix[i][j]. For the example matrix, the edges from cell (2,1) with value 1 point to (2,0) with value 2 and to (1,1) with value 6 — both are strictly greater.

(0,0)9 ← (1,0)6 ← (2,0)2
                     ↑
(0,1)9 ← (1,1)6 ← (2,1)1
                       
(0,2)4 → (1,2)8      (2,2)1

This DAG structure unlocks two efficient strategies:

1. DFS with memoization: compute the longest path from each node and cache results.
2. BFS topological sort: peel layers from the DAG starting at local minima, counting depth.

Both run in O(m * n) time — a massive improvement over brute force.

Approach 1: Brute Force DFS

The brute force approach starts DFS from every cell, exploring all four directions recursively. No caching, no pruning beyond the strict-increase check.

int longestPath(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int max = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            max = Math.max(max, dfs(matrix, i, j, rows, cols));
        }
    }
    return max;
}

int dfs(int[][] matrix, int i, int j, int rows, int cols) {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int best = 1;
    for (int[] d : dirs) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < rows && nj >= 0 && nj < cols
                && matrix[ni][nj] > matrix[i][j]) {
            best = Math.max(best, 1 + dfs(matrix, ni, nj, rows, cols));
        }
    }
    return best;
}

The time complexity is O(4^(m*n)) in the worst case. Each cell can branch into up to 4 neighbors, and without memoization, the same cell gets recomputed across different starting paths. For a 100×100 matrix, this is completely unusable.

Approach 2: DFS with Memoization

The brute force recomputes the longest path from the same cell many times. The fix: once you compute the longest path from cell (i, j), store it. Every future DFS that reaches (i, j) returns the cached result immediately.

memo[i][j] holds the longest increasing path starting from (i, j). If memo[i][j] > 0, it has already been computed — return it directly.

Implementation

record Dir(int dr, int dc) {}

static final Dir[] DIRECTIONS = {
    new Dir(0, 1), new Dir(0, -1),
    new Dir(1, 0), new Dir(-1, 0)
};

int longestIncreasingPath(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int[][] memo = new int[rows][cols];
    int longest = 0;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            longest = Math.max(longest, dfs(matrix, i, j, memo, rows, cols));
        }
    }
    return longest;
}

int dfs(int[][] matrix, int i, int j, int[][] memo, int rows, int cols) {
    if (memo[i][j] > 0) return memo[i][j];

    int best = 1;
    for (Dir d : DIRECTIONS) {
        int ni = i + d.dr(), nj = j + d.dc();
        if (inBounds(ni, nj, rows, cols)
                && matrix[ni][nj] > matrix[i][j]) {
            best = Math.max(best, 1 + dfs(matrix, ni, nj, memo, rows, cols));
        }
    }
    memo[i][j] = best;
    return best;
}

boolean inBounds(int r, int c, int rows, int cols) {
    return r >= 0 && r < rows && c >= 0 && c < cols;
}

The Dir record replaces the traditional int[][] direction array. It makes the intent explicit — each direction has a row delta and a column delta — and the compiler enforces the shape. The inBounds helper keeps the DFS method focused on logic rather than index gymnastics.

Walkthrough

Trace through the example matrix starting from cell (2, 1) with value 1:

1. DFS(2, 1): Value is 1. Check neighbors:

   • (2, 0) has value 2 > 1 → recurse
   • (1, 1) has value 6 > 1 → recurse
   • (2, 2) has value 1, not > 1 → skip

2. DFS(2, 0): Value is 2. Check neighbors:

   • (1, 0) has value 6 > 2 → recurse

3. DFS(1, 0): Value is 6. Check neighbors:

   • (0, 0) has value 9 > 6 → recurse

4. DFS(0, 0): Value is 9. No neighbor has a value > 9. Return memo[0][0] = 1.

5. Back to DFS(1, 0): Best path through (0, 0) is 1 + 1 = 2. No other valid neighbor. Set memo[1][0] = 2.

6. Back to DFS(2, 0): Best path through (1, 0) is 1 + 2 = 3. Set memo[2][0] = 3.

7. DFS(1, 1): Value is 6. Check neighbors:

   • (0, 1) has value 9 > 6 → memo[0][1] may already be computed or we recurse. Returns 1.
   • (1, 2) has value 8 > 6 → recurse. Returns 1 (no neighbor > 8 except 9 at (0, 2)? Actually (0, 2) is 4 < 8. So returns 1).
   • Best = 1 + 1 = 2. Set memo[1][1] = 2.

8. Back to DFS(2, 1): Path through (2, 0) gives 1 + 3 = 4. Path through (1, 1) gives 1 + 2 = 3. Best is 4. Set memo[2][1] = 4.

When DFS later starts from cell (1, 0), it finds memo[1][0] = 2 already filled. No recomputation. Each cell is computed exactly once.

Approach 3: BFS Topological Sort

The BFS approach takes a different angle. Instead of exploring from each cell, it processes cells in topological order by layer. Cells with the smallest values — those with no incoming edges (in-degree 0) — form the first layer. Peeling these away exposes the next layer, and so on. The number of layers equals the longest path length.

Computing In-Degree

For each cell (i, j), its in-degree is the count of neighbors with a strictly smaller value. A cell with in-degree 0 has no neighbor smaller than itself — it’s a local minimum and a potential path start.

Implementation

int longestIncreasingPath(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int[][] inDegree = new int[rows][cols];
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    // Compute in-degree for each cell
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            for (int[] d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols
                        && matrix[ni][nj] < matrix[i][j]) {
                    inDegree[i][j]++;
                }
            }
        }
    }

    // Enqueue all cells with in-degree 0
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (inDegree[i][j] == 0) {
                queue.offer(new int[]{i, j});
            }
        }
    }

    // BFS layer by layer
    int layers = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        layers++;
        for (int k = 0; k < size; k++) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            for (int[] d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols
                        && matrix[ni][nj] > matrix[i][j]) {
                    inDegree[ni][nj]--;
                    if (inDegree[ni][nj] == 0) {
                        queue.offer(new int[]{ni, nj});
                    }
                }
            }
        }
    }
    return layers;
}

Why BFS Works

Cells with in-degree 0 have no smaller neighbors — they must be the starting points of any increasing path. Processing them first peels away the “bottom layer” of the DAG. Their neighbors lose one incoming edge; when a neighbor’s in-degree drops to 0, all its predecessors have been processed, and it joins the next BFS layer.

Each layer represents one step deeper into the DAG. The total number of layers is the length of the longest path. Think of it as measuring the “depth” of the DAG by peeling it like an onion.

For the example matrix, the first layer contains cells with values 1 (local minima). The second layer adds value 2. The third adds value 6. The fourth adds value 9. Four layers, longest path = 4 — matching the DFS result.

Complexity Analysis

Approach	Time	Space	Notes
Brute Force DFS	O(4^(m·n))	O(m·n) stack	Exponential, unusable for real inputs
DFS + Memoization	O(m·n)	O(m·n)	Each cell computed exactly once
BFS Topological Sort	O(m·n)	O(m·n)	Layer-by-layer processing

Both optimal approaches visit each cell once and each edge once. The total number of edges is at most 4 * m * n (each cell has at most 4 neighbors), so the work per cell is constant amortized.

Space is O(m * n) in all cases: the memo table for DFS, or the in-degree array plus the queue for BFS. The recursion stack for DFS can reach O(m * n) depth in the worst case (a snaking path through the entire matrix), which the BFS approach avoids.

When to Use Which

DFS + Memoization is the default interview pick. It maps directly to the recursive thinking most candidates use: “what’s the longest path from here?” The code is shorter, the logic is linear, and the memoization pattern is widely recognized.

BFS Topological Sort shines when the interviewer asks for the actual path, not the length. Layer-by-layer processing naturally tracks predecessor information. It also avoids deep recursion stacks, making it preferable for very large matrices where stack overflow is a concern.

In practice, interviewers expect the DFS approach. Mentioning the BFS alternative demonstrates depth of understanding.

Edge Cases

• Single cell matrix: No moves possible. Return 1.
• All cells have the same value: No strictly increasing move exists. Every cell has path length 1.
• Entire matrix is strictly increasing in one direction: The path covers the entire matrix. Length = m * n. Example: a matrix where each row is sorted and each row’s minimum exceeds the previous row’s maximum.
• Very large matrix (1000×1000): DFS memoization may hit stack depth limits in languages without tail-call optimization. Java’s default stack size handles this for most cases, but the BFS approach eliminates the risk entirely.
• Matrix with only two distinct values: Paths have length at most 2. Any cell adjacent to a larger value contributes a path of length 2.

Interviewer Tips

Open with the DAG observation. Stating “the strict-increase constraint means there are no cycles, so this is a longest-path-in-a-DAG problem” signals graph-theoretic maturity before writing a single line of code.

DFS with memoization is the go-to implementation. It’s clean, well-understood, and directly addresses the problem. Write it confidently and walk through the memoization mechanics.

Common follow-up questions:

• Print the actual path, not the length. Track parent pointers during DFS, or use the BFS layer information to reconstruct the path backward from the endpoint.
• Allow diagonal movement. Expand the direction array to 8 entries. The algorithm stays the same; only the constant factor changes. The DAG property still holds because the strict-increase constraint prevents cycles regardless of direction count.
• What if the path must be non-decreasing (≥) instead of strictly increasing (>)? Cycles become possible (adjacent cells with equal values form a cycle). The DAG property breaks, and the problem becomes NP-hard in the general case. This is a critical distinction to point out.
• Can you do it without extra space? Not without the memo table. The memoization is essential to avoid exponential recomputation. You can argue the O(m * n) space is inherent to the problem structure.