Problem 24.7 · Topological SortHard

Longest Increasing Path in a Matrix

PatternTopological Sort Graph DFS and Flood Fill Grid DP

What it teaches: A grid with "move to a larger value" edges is a DAG, so memoised DFS (DP over the DAG) gives the longest path.

Practise it on judges as “Longest Increasing Path in a Matrix”.

The problem

Return the length of the longest strictly increasing path in a matrix, moving up, down, left or right.

Example 1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4

1 → 2 → 6 → 9.

Constraints

1 ≤ rows, cols ≤ 200

Pattern clues in the wording

→ Longest path where each step increases
→ No cycles possible

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	matrix = [[9,9,4],[6,6,8],[2,1,1]]	4
2	matrix = [[3,4,5],[3,2,6],[2,2,1]]	4
3	matrix = [[1]]	1

From slow to fast

Approaches

1. Memoised DFS · O(rows × cols)2. Kahn's by levels · O(rows × cols)

Memoised DFS

Time O(rows × cols) Space O(rows × cols)

memo[r][c] = 1 + max over neighbours with a larger value. Each cell is computed once.

Approach 1

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

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

    private int len(int[][] m, int r, int c) {
        if (memo[r][c] > 0) return memo[r][c];
        int best = 1;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= m.length || nc >= m[0].length || m[nr][nc] <= m[r][c]) continue;
            best = Math.max(best, 1 + len(m, nr, nc));
        }
        return memo[r][c] = best;
    }
}

Verdict: DP on the implicit DAG.

Kahn's by levels

Time O(rows × cols) Space O(rows × cols)

Edge from each cell to larger neighbours. Peel cells with no smaller neighbour (in-degree 0) level by level; the number of levels is the answer.

Approach 2

import java.util.*;

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int[][] indeg = new int[m][n];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nc >= 0 && nr < m && nc < n && matrix[nr][nc] < matrix[r][c]) indeg[r][c]++;
                }
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (indeg[r][c] == 0) q.offer(new int[]{r, c});
        int levels = 0;
        while (!q.isEmpty()) {
            levels++;
            for (int size = q.size(); size > 0; size--) {
                int[] cell = q.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n || matrix[nr][nc] <= matrix[cell[0]][cell[1]]) continue;
                    if (--indeg[nr][nc] == 0) q.offer(new int[]{nr, nc});
                }
            }
        }
        return levels;
    }
}

Verdict: Iterative: no recursion depth issues.

Before you submit

Edge cases and common mistakes

Test these inputs

All equal values (answer 1)
Single cell

Mistakes people make

Adding a visited set and resetting it per start (exponential without memo).

Interview

Follow-up questions

Why don't you need a visited set?