Longest Increasing Path in a Matrix

Hard Graphs Topological Sort Original on LeetCode

Longest Increasing Path in a Matrix is a hard graphs problem solved with the topological sort pattern. The best approach, optimal (topological peeling), runs in O(m · n) time and O(m · n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (dfs from every cell) up.

Problem

You are given an m x n grid of integers matrix. From any cell you may step to one of its four neighbours (up, down, left or right), but only if the neighbour holds a strictly larger value.

Return the number of cells in the longest path you can walk this way. A path may start at any cell, and a single cell counts as a path of length 1.

Examples

Example 1

Input
matrix = [[3,4,5],[2,9,6],[1,8,7]]
Output
9
Why
Start at 1 and walk 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9, a spiral through every cell.

Example 2

Input
matrix = [[5,5],[5,5]]
Output
1
Why
Equal neighbours do not count as increasing, so every path is a single cell.

Example 3

Input
matrix = [[1,10,2]]
Output
2
Why
1 → 10 or 2 → 10; you cannot continue past 10 because both of its neighbours are smaller.

Constraints

  • 1 <= m, n <= 200 where m and n are the number of rows and columns.
  • 0 <= matrix[i][j] <= 2^31 - 1
  • Moves go up, down, left or right; no diagonals and no wrapping around the border.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (DFS from every cell)O(4^(m·n)) worst caseO(m · n)
DFS with memoizationO(m · n)O(m · n)
Optimal (topological peeling)O(m · n)O(m · n)

1Brute force (DFS from every cell)

TimeO(4^(m·n)) worst caseThe same suffix of a path is recomputed for every path that reaches it, which grows exponentially.
SpaceO(m · n)Recursion depth can reach the length of the longest path.

From every cell, run a DFS that tries every larger neighbour and returns 1 plus the best result among them. Nothing is cached, so the same cells are explored again and again.

  1. For each cell (i, j), compute dfs(i, j) and keep the maximum.
  2. dfs(i, j) = 1 + max(dfs(neighbour)) over neighbours with a strictly larger value, or 1 if there are none.
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    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[][] g, int r, int c) {
        int best = 1;
        for (int[] d : DIRS) {
            int x = r + d[0], y = c + d[1];
            if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[r][c])
                best = Math.max(best, 1 + dfs(g, x, y));
        }
        return best;
    }
}

2DFS with memoization

TimeO(m · n)Each cell is computed once and looks at 4 neighbours.
SpaceO(m · n)The memo table, plus recursion that can be as deep as the longest path.

The longest path starting at a cell is the same no matter how you got there, so store it the first time you compute it. Every cell is then solved exactly once.

  1. memo[i][j] = 0 means not computed yet.
  2. dfs(i, j): if memo is set, return it; otherwise compute 1 + max over larger neighbours, store and return.
  3. Answer = max of dfs over all cells.
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    private int[][] memo;

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

    private int dfs(int[][] g, int r, int c) {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;
        for (int[] d : DIRS) {
            int x = r + d[0], y = c + d[1];
            if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[r][c])
                best = Math.max(best, 1 + dfs(g, x, y));
        }
        return memo[r][c] = best;
    }
}

3Optimal (topological peeling)

TimeO(m · n)Every cell enters the queue once and checks its 4 neighbours.
SpaceO(m · n)The in-degree table and the queue.

Treat each cell as a node with an edge to every strictly larger neighbour. The graph has no cycles. Count, for each cell, how many smaller neighbours point into it; cells with count 0 are local minimums and form the first layer. Remove a layer, lower the counts of the cells it points to, and the cells that drop to 0 form the next layer. The number of layers is the length of the longest path, and no recursion is needed.

  1. indeg[i][j] = number of neighbours with a smaller value.
  2. Put every cell with indeg 0 in a queue; layers = 0.
  3. While the queue is not empty: layers++, and for each cell in the current layer, decrement indeg of every larger neighbour, adding it to the queue when it reaches 0.
  4. Return layers.
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];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                for (int[] d : dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] < matrix[i][j]) indeg[i][j]++;
                }
                if (indeg[i][j] == 0) q.add(new int[] { i, j });
            }
        int layers = 0;
        while (!q.isEmpty()) {
            layers++;
            for (int size = q.size(); size > 0; size--) {
                int[] c = q.poll();
                for (int[] d : dirs) {
                    int x = c[0] + d[0], y = c[1] + d[1];
                    if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[c[0]][c[1]]
                            && --indeg[x][y] == 0)
                        q.add(new int[] { x, y });
                }
            }
        }
        return layers;
    }
}

Edge cases to test

  • A single cell (answer 1)
  • All values equal (answer 1)
  • A snake-shaped path that visits every cell
  • A single row or a single column

Hints

Hint 1

A strictly increasing path can never return to a cell it already used, so there are no cycles to worry about.

Hint 2

The longest path starting at a cell depends only on that cell, not on how you reached it. Can you cache it?

Hint 3

Alternatively, think of each cell as a node with an edge to every larger neighbour: the answer is the number of layers when you peel the graph from its sinks (or sources) like a topological sort.

FAQ

What is the best time complexity for Longest Increasing Path in a Matrix?

Optimal (topological peeling) runs in O(m · n) time and O(m · n) extra space. Every cell enters the queue once and checks its 4 neighbours.

Which pattern does Longest Increasing Path in a Matrix use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Longest Increasing Path in a Matrix?

Yes. Brute force (DFS from every cell) takes O(4^(m·n)) worst case time and O(m · n) space. From every cell, run a DFS that tries every larger neighbour and returns 1 plus the best result among them.

Which edge cases should I test for Longest Increasing Path in a Matrix?

A single cell (answer 1); All values equal (answer 1); A snake-shaped path that visits every cell; A single row or a single column.