Longest Increasing Path in a Matrix

LeetCode 329: Longest Increasing Path in a Matrix Solution & Explanation

Problem Overview

TL;DR: Model each valid increasing move as a directed edge, then use 2D dynamic programming with indegree-based topological traversal to process cells from lower values to higher values and count the longest path length.

In LeetCode 329, Longest Increasing Path in a Matrix, the goal is to find the maximum number of cells that can be visited in a path where every move goes to an orthogonally adjacent cell with a strictly greater value. Movement outside the matrix and diagonal movement are not allowed.

This LeetCode 329 Solution uses the 2D Array dynamic programming pattern together with topological processing. Every cell is processed only after all lower-valued neighboring cells that can precede it have been processed.

Brute Force Approach for Longest Increasing Path in a Matrix

A direct approach starts a depth-first search from every cell:

1. Treat the current cell as the first cell in the path.
2. Check all four adjacent cells.
3. Recursively continue only to adjacent cells with larger values.
4. Return the longest path found from the current cell.
5. Take the maximum result over every starting cell.

Naive Pseudocode

function dfs(row, col):
    best = 1

    for each of the four directions:
        nextRow, nextCol = adjacent cell

        if next cell is inside the matrix
           and matrix[nextRow][nextCol] > matrix[row][col]:
            best = max(best, 1 + dfs(nextRow, nextCol))

    return best

answer = 0

for every cell (row, col):
    answer = max(answer, dfs(row, col))

return answer

Complexity

Let R be the number of rows and C the number of columns.

The search may explore a very large number of distinct increasing paths. Although values strictly increase along every path, the number of valid paths can still grow exponentially with the number of cells.

The worst-case time complexity is therefore exponential in the size of the matrix, commonly expressed as:

O(RC × number of increasing paths)

The recursion stack can use up to O(RC) space.

Why the Brute Force Approach Fails

Different starting cells frequently reach the same intermediate cell. Without storing results, the brute-force method recomputes the longest path from that cell repeatedly.

With up to 200 × 200 = 40,000 cells, this repeated exploration can cause Time Limit Exceeded. The key optimization is to ensure that each cell's path information is computed or finalized only once.

Algorithm Strategy: Dynamic Programming (DP) Patterns

1. Create an indegree matrix with one entry per cell.
2. For every cell, inspect its four orthogonal neighbors.
3. Increment the cell's indegree for every neighboring value that is smaller.
4. Add all cells with indegree 0 to a queue.
5. Process the queue in topological order:
   • For each current cell, inspect adjacent larger cells.
   • Decrease each larger cell's indegree.
   • Update its dynamic programming path length.
   • Add it to the queue when its indegree becomes 0.
6. Return the largest path length encountered.

The matrix boundaries are enforced before every neighbor access. Equal-valued neighbors are ignored because the path must be strictly increasing.

Execution Flow

1. Build predecessor counts

   • For each position (row, col), inspect up to four neighbors.
   • Every smaller neighbor represents a valid incoming edge.
   • Store the number of these incoming edges in indegree[row][col].

2. Initialize the queue

   • Add every cell whose indegree is 0.
   • These cells have no smaller adjacent predecessor and form the first topological layer.
   • Their initial path length is 1.

3. Process a ready cell

   • Remove a cell from the front of the queue.
   • Its current dynamic programming value represents the longest increasing path that reaches it.
   • Update the global answer using this value.

4. Relax larger neighbors

   • For each adjacent cell with a larger value:
     • Update the neighbor's path length using the current cell.
     • Decrease the neighbor's indegree because one predecessor has now been processed.
   • If the indegree reaches 0, enqueue the neighbor.

5. Finish after all layers

   • Every cell is eventually processed because the increasing-value graph is acyclic.
   • The maximum stored path length is the longest valid increasing path.

In the C++ implementation, queue elements are processed in batches. pathLength increases once per batch, so the number of batches equals the longest path length. In Java and Python, each cell explicitly stores its best path length.

Proof of Correctness

We prove that the algorithm returns the length of the longest strictly increasing path.

Claim 1: Every edge represents a valid path move

An edge is processed from a cell to an orthogonally adjacent cell only when the destination value is strictly greater than the source value. Therefore, every directed edge corresponds exactly to one valid move in the problem.

Claim 2: The directed graph is acyclic

Along every directed edge, the matrix value strictly increases. A directed cycle would require returning to the original cell after a sequence of strict increases, implying that the original value is greater than itself. This is impossible. Therefore, the graph is acyclic.

Claim 3: A cell is processed only after all of its smaller predecessors

The indegree of a cell counts all adjacent smaller cells that can lead into it. Each predecessor decreases this indegree once it is processed. The cell enters the queue only when its indegree becomes 0, so all valid smaller predecessors have already been processed.

Claim 4: The DP value for every processed cell is optimal

When a cell is processed, every possible predecessor has already been processed. For each predecessor, the algorithm considers:

length[cell] = max(length[cell], length[predecessor] + 1)

Thus, length[cell] becomes the maximum length of any increasing path ending at that cell.

Claim 5: The returned maximum is the global optimum

Every valid increasing path ends at some matrix cell. By Claim 4, the algorithm computes the maximum path length ending at every cell. Taking the maximum over all cells therefore returns the longest increasing path in the matrix.

Hence, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 120: Triangle
• LeetCode 63: Unique Paths II
• LeetCode 64: Minimum Path Sum
• LeetCode 1277: Count Square Submatrices with All Ones

These problems maintain a dynamic programming state for each position in a 2D structure. Each state is computed from related neighboring or preceding states while respecting grid boundaries and problem-specific transitions. In LeetCode 329, the additional ordering constraint is enforced through indegree-based processing of strictly increasing transitions, making it a useful variation of the 2D Array dynamic programming pattern and a popular interview question.

Reference Implementation

C++ Solution for LeetCode 329

1class Solution {
2public:
3    int longestIncreasingPath(vector<vector<int>>& matrix) {
4        int rows = matrix.size();
5        int cols = matrix[0].size();
6        vector<vector<int>> indegree(rows, vector<int>(cols, 0));
7        queue<pair<int, int>> q;
8        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
9
10        for (int r = 0; r < rows; ++r) {
11            for (int c = 0; c < cols; ++c) {
12                for (const auto& direction : directions) {
13                    int nr = r + direction[0];
14                    int nc = c + direction[1];
15                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
16                        matrix[nr][nc] < matrix[r][c]) {
17                        ++indegree[r][c];
18                    }
19                }
20                if (indegree[r][c] == 0) {
21                    q.push({r, c});
22                }
23            }
24        }
25
26        int pathLength = 0;
27        while (!q.empty()) {
28            int levelSize = q.size();
29            ++pathLength;
30
31            while (levelSize-- > 0) {
32                auto [r, c] = q.front();
33                q.pop();
34
35                for (const auto& direction : directions) {
36                    int nr = r + direction[0];
37                    int nc = c + direction[1];
38                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
39                        matrix[nr][nc] > matrix[r][c]) {
40                        if (--indegree[nr][nc] == 0) {
41                            q.push({nr, nc});
42                        }
43                    }
44                }
45            }
46        }
47
48        return pathLength;
49    }
50};

Java Solution for LeetCode 329

1class Solution {
2    public int longestIncreasingPath(int[][] matrix) {
3        int rows = matrix.length;
4        int cols = matrix[0].length;
5        int[][] indegree = new int[rows][cols];
6        int[][] length = new int[rows][cols];
7        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
8
9        for (int row = 0; row < rows; row++) {
10            for (int col = 0; col < cols; col++) {
11                length[row][col] = 1;
12                int value = matrix[row][col];
13                for (int[] direction : directions) {
14                    int nr = row + direction[0];
15                    int nc = col + direction[1];
16                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
17                            && matrix[nr][nc] < value) {
18                        indegree[row][col]++;
19                    }
20                }
21            }
22        }
23
24        java.util.ArrayDeque<int[]> queue = new java.util.ArrayDeque<>();
25        for (int row = 0; row < rows; row++) {
26            for (int col = 0; col < cols; col++) {
27                if (indegree[row][col] == 0) {
28                    queue.offer(new int[]{row, col});
29                }
30            }
31        }
32
33        int answer = 1;
34        while (!queue.isEmpty()) {
35            int[] cell = queue.poll();
36            int row = cell[0];
37            int col = cell[1];
38            answer = Math.max(answer, length[row][col]);
39
40            for (int[] direction : directions) {
41                int nr = row + direction[0];
42                int nc = col + direction[1];
43                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
44                        && matrix[nr][nc] > matrix[row][col]) {
45                    length[nr][nc] = Math.max(length[nr][nc], length[row][col] + 1);
46                    indegree[nr][nc]--;
47                    if (indegree[nr][nc] == 0) {
48                        queue.offer(new int[]{nr, nc});
49                    }
50                }
51            }
52        }
53
54        return answer;
55    }
56}

Python Solution for LeetCode 329

1from typing import List, Optional
2from collections import deque
3
4class Solution:
5    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
6        rows = len(matrix)
7        cols = len(matrix[0])
8        indegree = [[0] * cols for _ in range(rows)]
9        length = [[1] * cols for _ in range(rows)]
10        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
11
12        for row in range(rows):
13            for col in range(cols):
14                value = matrix[row][col]
15                for dr, dc in directions:
16                    nr, nc = row + dr, col + dc
17                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < value:
18                        indegree[row][col] += 1
19
20        queue = deque()
21        for row in range(rows):
22            for col in range(cols):
23                if indegree[row][col] == 0:
24                    queue.append((row, col))
25
26        answer = 1
27        while queue:
28            row, col = queue.popleft()
29            answer = max(answer, length[row][col])
30
31            for dr, dc in directions:
32                nr, nc = row + dr, col + dc
33                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[row][col]:
34                    length[nr][nc] = max(length[nr][nc], length[row][col] + 1)
35                    indegree[nr][nc] -= 1
36                    if indegree[nr][nc] == 0:
37                        queue.append((nr, nc))
38
39        return answer