HardArrayDynamic ProgrammingDepth-First SearchBreadth-First SearchGraphTopological SortMemoizationMatrix

Longest Increasing Path in a Matrix

1 approach, code in every language

You are given an m x n grid of integers. Starting from any cell you may repeatedly move to one of the four horizontally or vertically adjacent cells, but only when the value of the destination cell is strictly greater than the value of the current cell.

A path is the sequence of cells visited by such moves, and its length is the number of cells it contains. You may begin and end at any cells you like, and diagonal moves or wrapping around the borders are not permitted.

Return the length of the longest strictly increasing path that can be formed in the grid.

Example 1

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

Output: 4

The longest increasing path is 1 -> 2 -> 6 -> 9, which visits four cells.

Example 2

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output: 4

The path 3 -> 4 -> 5 -> 6 is the longest; equal values cannot be chained because moves must be strictly increasing.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

DFS over the Implicit DAG with Memoization

Treat every strictly increasing move as a DAG edge and cache the longest path starting at each cell.

Loading animation…

Intuition

Because every move must go to a strictly larger value, no path can ever revisit a cell, so the grid behaves like a directed acyclic graph. The longest increasing path that starts at a cell depends only on the longest increasing paths starting at its larger neighbors, which makes the problem a natural fit for recursion. Once we compute the best length for a cell we never need to recompute it, so a memo table turns an exponential search into linear work. The overall answer is the maximum starting length taken over every cell in the grid.

Algorithm walkthrough

1Create a memo grid the same size as the matrix, initialized to zero to mark cells whose answer is not yet known.
2Define a recursive function that, for a given cell, returns the length of the longest increasing path beginning there.
3Inside the recursion look at the four neighbors; whenever a neighbor holds a strictly larger value, recurse into it and consider one plus that result.
4Take the best value among all valid neighbors (at least one for the cell itself), store it in the memo, and return it.
5Call the function for every cell and return the largest value produced.

Implementation

from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        memo = [[0] * cols for _ in range(rows)]
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> int:
            if memo[r][c]:
                return memo[r][c]
            best = 1
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            memo[r][c] = best
            return best

        return max(dfs(r, c) for r in range(rows) for c in range(cols))

Time

O(m * n)

Space

O(m * n)

Each cell is solved once and cached; recursion depth is bounded by the number of cells.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Tallest Stack Ascent is our own problem on the technique behind Longest Increasing Path in a Matrix: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free