Longest Increasing Path in a Matrix

Description

You are given an m × n matrix of integers. Your task is to find the length of the longest strictly increasing path in this matrix.

From any cell, you can move in four directions: up, down, left, or right (no diagonal moves). You cannot move outside the matrix boundaries, and wrapping around is not allowed.

A path is considered increasing if every cell you move to has a strictly greater value than the cell you just came from. The path can start from any cell in the matrix.

Return the length of the longest such path.

3x3 grid showing the matrix [[9,9,4],[6,6,8],[2,1,1]] with the longest increasing path [1,2,6,9] highlighted in green

Examples

Example 1

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

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9]. Starting at cell (2,1) with value 1, we move left to (2,0) with value 2, then up to (1,0) with value 6, then up to (0,0) with value 9. Each step is strictly increasing: 1 < 2 < 6 < 9. No longer increasing path exists in this matrix.

Example 2

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

Output: 4

Explanation: The longest increasing path is [3, 4, 5, 6]. Starting at cell (1,0) with value 3, move right to (0,1) with value 4 — wait, (0,1) is not adjacent to (1,0)? Actually, moving up from (1,0) to (0,0) gives 3→3 which is not strictly increasing. Instead, the path starts at (0,0)=3, moves right to (0,1)=4, right to (0,2)=5, down to (1,2)=6. Each step is strictly increasing. Note: diagonal moves are not allowed.

Example 3

Input: matrix = [[1]]

Output: 1

Explanation: The matrix has only one cell. The longest path contains just that single cell, so the answer is 1.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is: from every cell in the matrix, explore all possible increasing paths using Depth-First Search, and return the length of the longest one found.

Think of it like exploring a mountainous terrain where you can only walk uphill. You start from every valley and hilltop, walk in every possible uphill direction as far as you can, and measure the longest trail you discover.

For each cell, we recursively try all four directions. If a neighboring cell has a strictly greater value, we continue the path into that neighbor. The path length from the current cell is 1 (for itself) plus the longest path achievable from any valid neighbor.

Because values must strictly increase, we can never revisit a cell within the same path — the path forms a chain of strictly increasing values, which means no cycles are possible. So we don't need a visited array.

Step-by-Step Explanation

Let's trace through with matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]:

Step 1: Start DFS from (0,0), value 9. Check all 4 neighbors:

Up: out of bounds. Down: (1,0)=6, not > 9. Left: out of bounds. Right: (0,1)=9, not > 9.
No valid moves. Path length from (0,0) = 1.

Step 2: Start DFS from (0,1), value 9. All neighbors ≤ 9. Path length = 1.

Step 3: Start DFS from (0,2), value 4. Neighbors > 4: (0,1)=9 and (1,2)=8.

Recurse into (0,1)=9: no moves from 9, returns 1.
Recurse into (1,2)=8: neighbors > 8 → none (up (0,2)=4, left (1,1)=6, down (2,2)=1). Returns 1.
Best extension = max(1, 1) = 1. Path length from (0,2) = 1 + 1 = 2.

Step 4: Start DFS from (1,0), value 6. Neighbor > 6: (0,0)=9.

Recurse into (0,0)=9: returns 1.
Path length from (1,0) = 1 + 1 = 2.

Step 5: Start DFS from (1,1), value 6. Neighbors > 6: (0,1)=9, (1,2)=8.

Recurse into (0,1)=9: returns 1. But wait — we already computed this from Step 2! Without memoization, we compute it again from scratch.
Recurse into (1,2)=8: returns 1. Again, we already computed this in Step 3's sub-call.
Path length from (1,1) = 1 + max(1, 1) = 2.

Step 6: Start DFS from (2,1), value 1. Neighbors > 1: (2,0)=2, (1,1)=6.

Recurse into (2,0)=2: this triggers DFS(2,0) → DFS(1,0) → DFS(0,0). Each of these is recomputed from scratch!
Returns: DFS(2,0)=3 (path 2→6→9).
Recurse into (1,1)=6: triggers DFS(1,1) → DFS(0,1) and DFS(1,2). All recomputed again!
Returns: DFS(1,1)=2.
Path length from (2,1) = 1 + max(3, 2) = 4.

Step 7: After checking all 9 cells, the maximum path length is 4, achieved starting from cell (2,1). The path is [1, 2, 6, 9].

Key observation: Without memoization, cells like (0,0) and (0,1) are recomputed many times from different starting points, leading to massive redundancy.

Algorithm

For each cell (r, c) in the matrix:
- Call dfs(r, c, -∞) where the third parameter is the previous value
- Track the maximum result across all starting cells
In dfs(r, c, prevVal):
- If (r, c) is out of bounds or matrix[r][c] ≤ prevVal, return 0
- Initialize best = 1 (current cell counts)
- For each of the 4 directions (up, down, left, right):
  - Recursively call dfs(neighbor) with matrix[r][c] as the new prevVal
  - Update best = max(best, 1 + recursive result)
- Return best
Return the maximum path length found

Code

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        int result = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result = max(result, dfs(matrix, r, c, -1, rows, cols));
            }
        }
        return result;
    }

private:
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

    int dfs(vector<vector<int>>& matrix, int r, int c,
            int prevVal, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
        if (matrix[r][c] <= prevVal) return 0;

        int best = 1;
        for (auto& d : dirs) {
            best = max(best, 1 + dfs(matrix, r + d[0], c + d[1],
                                     matrix[r][c], rows, cols));
        }
        return best;
    }
};

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r, c, prev_val):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return 0
            if matrix[r][c] <= prev_val:
                return 0

            best = 1
            for dr, dc in directions:
                best = max(best, 1 + dfs(r + dr, c + dc, matrix[r][c]))
            return best

        result = 0
        for r in range(rows):
            for c in range(cols):
                result = max(result, dfs(r, c, float('-inf')))
        return result

class Solution {
    private int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    private int rows, cols;

    public int longestIncreasingPath(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;
        int result = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result = Math.max(result, dfs(matrix, r, c, -1));
            }
        }
        return result;
    }

    private int dfs(int[][] matrix, int r, int c, int prevVal) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
        if (matrix[r][c] <= prevVal) return 0;

        int best = 1;
        for (int[] d : dirs) {
            best = Math.max(best, 1 + dfs(matrix, r + d[0], c + d[1], matrix[r][c]));
        }
        return best;
    }
}

Complexity Analysis

Time Complexity: O(m × n × 4^(m×n))

For each of the m×n cells, we start a DFS that can branch into up to 4 directions at each step. In the worst case (a matrix with all unique values forming a long path), a DFS call from one cell could explore paths of length up to m×n, with up to 4 branches at each level. This creates an exponential number of recursive calls. Without memoization, the same sub-paths are recomputed repeatedly from different starting cells, multiplying the work enormously.

Space Complexity: O(m × n)

The recursion stack can go as deep as m×n in the worst case (if the entire matrix forms one long increasing path, like a spiral of increasing values). Each stack frame stores constant data, so the space is proportional to the maximum recursion depth.

Why This Approach Is Not Efficient

The brute force DFS recomputes the same cells over and over. Consider cell (0,0) with value 9 in our example: it's a dead end (no neighbors > 9), so the longest path from it is always 1. But the brute force computes this fact every time any path reaches (0,0) — from (1,0), from (0,1), and indirectly from (2,0), (2,1), (1,1), etc.

With matrix dimensions up to 200×200 = 40,000 cells, the exponential branching makes this approach hopelessly slow. Even for modest inputs, the brute force times out.

The critical insight is that the longest increasing path from cell (r, c) depends only on (r, c) itself — not on how you arrived there. Since values must strictly increase, the path from (r, c) is always the same regardless of the starting cell. This means the DFS has overlapping subproblems with optimal substructure, which is the classic signature for dynamic programming.

If we cache (memoize) the result for each cell after computing it once, every subsequent query for that cell returns instantly in O(1). Since there are only m×n cells and each is computed exactly once, the total work drops from exponential to O(m×n).

Optimal Approach - DFS With Memoization

Intuition

The key realization is that the matrix, when we draw edges only from smaller values to larger neighbors, forms a Directed Acyclic Graph (DAG). Values must strictly increase along any path, so you can never loop back to a cell you've already visited — cycles are impossible.

In a DAG, finding the longest path is a well-studied problem that can be solved efficiently with memoization. We define:

memo[r][c] = length of the longest increasing path starting from cell (r, c)

For any cell (r, c), we look at its four neighbors. If a neighbor has a strictly greater value, the path can extend through that neighbor. So:

memo[r][c] = 1 + max(memo[nr][nc] for all valid neighbors (nr, nc) where matrix[nr][nc] > matrix[r][c])

If no neighbor has a greater value, then memo[r][c] = 1 (just the cell itself).

Imagine you're mapping hiking trails on a mountain. Once you've figured out the longest uphill trail from a particular campsite, you write it on a sign at that campsite. Next time anyone asks 'what's the longest trail from here?', they just read the sign — no need to re-explore the entire mountain. That's memoization: compute once, reuse forever.

We DFS from every cell, but thanks to caching, each cell is actually computed at most once. The total work is proportional to the number of cells times the constant work per cell (checking 4 neighbors).

Step-by-Step Explanation

Let's trace through with matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]:

Step 1: Initialize an empty memo table. Start iterating through all cells in row-major order.

Step 2: DFS(0,0), value 9. Check neighbors: down (1,0)=6 ≤ 9, right (0,1)=9 ≤ 9. No neighbor > 9. memo[0][0] = 1.

Step 3: DFS(0,1), value 9. No neighbor > 9. memo[0][1] = 1.

Step 4: DFS(0,2), value 4. Neighbors > 4: left (0,1)=9, down (1,2)=8. Need to recurse into both.

Step 5: Check (0,1) — it's already in the memo! memo[0][1] = 1. Cache hit — no recomputation needed.

Step 6: Recurse into (1,2), value 8. Check neighbors > 8: up (0,2)=4, down (2,2)=1, left (1,1)=6. None > 8. memo[1][2] = 1.

Step 7: Back at (0,2): best neighbor path = max(memo[0][1], memo[1][2]) = max(1, 1) = 1. memo[0][2] = 1 + 1 = 2.

Step 8: DFS(1,0), value 6. Neighbor > 6: up (0,0)=9 → cache hit! memo[0][0] = 1. memo[1][0] = 1 + 1 = 2.

Step 9: DFS(1,1), value 6. Neighbors > 6: up (0,1)=9 → cache hit (1), right (1,2)=8 → cache hit (1). memo[1][1] = 1 + max(1, 1) = 2.

Step 10: DFS(2,0), value 2. Neighbor > 2: up (1,0)=6 → cache hit! memo[1][0] = 2. memo[2][0] = 1 + 2 = 3.

Step 11: DFS(2,1), value 1. Neighbors > 1: left (2,0)=2 → cache hit (3), up (1,1)=6 → cache hit (2). Best = max(3, 2) = 3. memo[2][1] = 1 + 3 = 4.

Step 12: DFS(2,2), value 1. Neighbor > 1: up (1,2)=8 → cache hit (1). memo[2][2] = 1 + 1 = 2.

Step 13: All cells computed. Maximum across all memo values = 4 (at cell (2,1)). The longest increasing path is [1 → 2 → 6 → 9].

DFS with Memoization — Computing Longest Increasing Paths — Watch how memoization prevents redundant DFS calls. Each cell is computed at most once; subsequent visits return the cached value instantly.

Algorithm

Initialize an empty memo dictionary (or m×n table of -1)
Define dfs(r, c):
- If (r, c) is already in memo, return memo[(r, c)]
- Initialize best = 1 (the current cell itself)
- For each of the 4 directions (up, down, left, right):
  - If the neighbor (nr, nc) is in bounds AND matrix[nr][nc] > matrix[r][c]:
    - best = max(best, 1 + dfs(nr, nc))
- Store memo[(r, c)] = best and return it
For every cell (r, c) in the matrix:
- Call dfs(r, c) and track the global maximum
Return the global maximum

Code

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        // Memo table: -1 means not computed yet
        vector<vector<int>> memo(rows, vector<int>(cols, -1));
        int result = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result = max(result, dfs(matrix, memo, r, c, rows, cols));
            }
        }
        return result;
    }

private:
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo,
            int r, int c, int rows, int cols) {
        if (memo[r][c] != -1) return memo[r][c];

        int best = 1;
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && matrix[nr][nc] > matrix[r][c]) {
                best = max(best, 1 + dfs(matrix, memo, nr, nc, rows, cols));
            }
        }
        memo[r][c] = best;
        return best;
    }
};

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        memo = {}

        def dfs(r, c):
            if (r, c) in memo:
                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

        result = 0
        for r in range(rows):
            for c in range(cols):
                result = max(result, dfs(r, c))
        return result

class Solution {
    private int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    private int rows, cols;
    private int[][] memo;

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

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result = Math.max(result, dfs(matrix, r, c));
            }
        }
        return result;
    }

    private int dfs(int[][] matrix, 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 && nr < rows && nc >= 0 && nc < cols
                && matrix[nr][nc] > matrix[r][c]) {
                best = Math.max(best, 1 + dfs(matrix, nr, nc));
            }
        }
        memo[r][c] = best;
        return best;
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We call DFS from each of the m×n cells in the outer loop. However, due to memoization, the actual DFS computation for each cell happens at most once. When a cell is visited again (either from the outer loop or from another cell's DFS), the cached result is returned in O(1). Within each cell's computation, we check at most 4 neighbors — constant work. So the total time is O(m × n) cells × O(1) work per cell = O(m × n).

Space Complexity: O(m × n)

The memo table stores one integer per cell, requiring O(m × n) space. The recursion stack can reach depth O(m × n) in the worst case — imagine a matrix where values form a single long increasing path (like a spiral). Each stack frame uses O(1) space, so the stack contributes O(m × n). Total space: O(m × n).

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Longest Increasing Path in a Matrix

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - DFS With Memoization

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis