LeetCode 329 - Longest Increasing Path in a Matrix

LeetCode Problem 329

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort, Memoization, Matrix

Solution

Problem Understanding

The problem gives us a two-dimensional grid of integers called matrix. Each position in the grid contains a value, and we are asked to find the length of the longest strictly increasing path.

A path starts from any cell and moves one step at a time in one of four directions: up, down, left, or right. Diagonal movement is not allowed, and we cannot move outside the matrix boundaries. A move is valid only if the destination cell contains a strictly larger value than the current cell.

The result we return is not the path itself, but the number of cells in the longest valid increasing sequence.

For example, consider the matrix:

[
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
]

One valid increasing path is:

1 -> 2 -> 6 -> 9

This path has length 4, which is the maximum possible, so the answer is 4.

The constraints are important:

• m and n can each be as large as 200
• The matrix may therefore contain up to 40,000 cells
• Cell values can be very large integers

A naive recursive exploration from every cell can quickly become prohibitively expensive because many subproblems overlap. The same cell may be revisited repeatedly while computing paths from different starting positions.

Several edge cases are especially important:

• A matrix with only one cell should return 1
• A matrix where all values are identical should also return 1, because no increasing move exists
• Strictly decreasing matrices still return 1 for every starting point
• Multiple paths may converge into the same subpath, which creates heavy repeated computation in naive solutions
• Large matrices require an efficient solution because exponential exploration would time out

This problem is fundamentally a graph problem disguised as a matrix problem. Each cell can be viewed as a node, and edges exist from smaller values to larger neighboring values. Because values must strictly increase, cycles are impossible, which makes the graph a Directed Acyclic Graph, or DAG.

Approaches

Brute Force Approach

The most direct solution is to start a depth-first search from every cell in the matrix.

For each starting cell, we recursively try moving in all four directions. Whenever a neighboring cell contains a larger value, we continue the search from that neighbor. We compute the maximum path length reachable from the current cell and return it.

This approach is correct because it exhaustively explores every valid increasing path.

The problem is that it recomputes the same subproblems many times. Suppose multiple paths reach the same cell. Each time we arrive at that cell, we recursively recompute the longest path starting from it. This duplication grows exponentially in the worst case.

For a matrix of size 200 x 200, brute force recursion becomes completely impractical.

Key Insight

The crucial observation is that the longest increasing path starting from a particular cell is always the same, regardless of how we reached that cell.

This means the problem has overlapping subproblems, which makes it a perfect candidate for memoization.

Instead of recomputing the answer for a cell repeatedly, we compute it once and cache the result. Future calls simply reuse the stored value.

Because paths must strictly increase, cycles cannot exist. We therefore have a DAG structure, and DFS with memoization efficiently computes the longest path from every node exactly once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^(m*n)) worst case	O(m*n) recursion stack	Recomputes the same paths repeatedly
Optimal DFS + Memoization	O(m*n)	O(m*n)	Each cell is computed once and cached

Algorithm Walkthrough

Optimal DFS + Memoization Algorithm

1. Create a memoization table with the same dimensions as the matrix.

Each entry memo[row][col] stores the length of the longest increasing path starting from that cell. Initially, all values are 0, meaning "not computed yet." 2. Define the four possible movement directions.

We only allow:

• up
• down
• left
• right

These directions are stored in a small list so we can iterate cleanly during DFS. 3. Define a DFS function.

The DFS function computes the longest increasing path beginning at a specific cell.

If the result for the current cell already exists in the memo table, immediately return it. This avoids recomputation. 4. Initialize the current cell's best path length as 1.

Every cell by itself forms a valid increasing path of length 1. 5. Explore all four neighboring cells.

For each neighbor:

• Check boundary conditions
• Check whether the neighbor value is strictly larger

If both conditions are satisfied, recursively compute the longest path from the neighbor. 6. Update the current cell's answer.

If moving to a neighbor produces a longer path, update the best value:

best = max(best, 1 + dfs(neighbor))

7. Store the computed result in the memo table.

Once all neighbors are processed, save the final answer for this cell. 8. Run DFS from every cell.

Since the longest overall path could begin anywhere, iterate through the entire matrix and compute:

answer = max(answer, dfs(row, col))

9. Return the global maximum.

Why it works

The algorithm works because every increasing path forms a DAG. Since values must strictly increase, cycles are impossible. DFS explores all reachable increasing paths from a cell, while memoization guarantees that each cell's result is computed only once.

The invariant is:

memo[row][col] =
length of the longest increasing path starting at (row, col)

Because all recursive dependencies move toward strictly larger values, previously computed results are always valid and reusable.

Python Solution

from typing import List

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

        memo = [[0] * cols for _ in range(rows)]

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]

        def dfs(row: int, col: int) -> int:
            if memo[row][col] != 0:
                return memo[row][col]

            longest = 1

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and matrix[new_row][new_col] > matrix[row][col]
                ):
                    candidate = 1 + dfs(new_row, new_col)
                    longest = max(longest, candidate)

            memo[row][col] = longest
            return longest

        answer = 0

        for row in range(rows):
            for col in range(cols):
                answer = max(answer, dfs(row, col))

        return answer

The implementation begins by determining the matrix dimensions and allocating a memoization table. Each entry in memo stores the computed longest path starting from that cell.

The directions list centralizes movement logic and avoids repetitive code for neighbor traversal.

The dfs function performs the core computation. The first operation checks whether the current cell has already been solved. If so, the cached result is returned immediately.

The variable longest starts at 1 because the current cell itself forms a valid path.

The function then iterates through all neighboring positions. For each valid increasing neighbor, it recursively computes the neighbor's longest path and extends it by one.

After all neighbors are explored, the computed result is stored in memo[row][col].

Finally, the outer loops start DFS from every cell and track the global maximum path length.

Go Solution

func longestIncreasingPath(matrix [][]int) int {
	rows := len(matrix)
	cols := len(matrix[0])

	memo := make([][]int, rows)
	for i := range memo {
		memo[i] = make([]int, cols)
	}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	var dfs func(int, int) int

	dfs = func(row int, col int) int {
		if memo[row][col] != 0 {
			return memo[row][col]
		}

		longest := 1

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow >= 0 &&
				newRow < rows &&
				newCol >= 0 &&
				newCol < cols &&
				matrix[newRow][newCol] > matrix[row][col] {

				candidate := 1 + dfs(newRow, newCol)

				if candidate > longest {
					longest = candidate
				}
			}
		}

		memo[row][col] = longest
		return longest
	}

	answer := 0

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			current := dfs(row, col)

			if current > answer {
				answer = current
			}
		}
	}

	return answer
}

The Go implementation closely mirrors the Python solution. The main difference is explicit slice allocation for the memo table and the use of a function variable for recursive DFS.

Go does not support nested named functions directly, so we declare dfs as a variable before assigning the recursive closure.

Integer overflow is not a concern because the maximum path length is bounded by the number of cells, at most 40,000.

Go slices are used instead of fixed-size arrays because matrix dimensions are determined at runtime.

Worked Examples

Example 1

Input:

[
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
]

We begin DFS from every cell.

DFS from cell (2,1) with value 1

Possible moves:

Neighbor	Value	Valid Increasing Move
Up (1,1)	6	Yes
Down	Out of bounds	No
Left (2,0)	2	Yes
Right (2,2)	1	No

We recursively explore both valid paths.

Path through 2

1 -> 2 -> 6 -> 9

Memo values become:

Cell	Longest Path
9	1
6	2
2	3
1	4

Final answer becomes 4.

Example 2

Input:

[
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

The longest path is:

3 -> 4 -> 5 -> 6

DFS progression

Cell	Computed Path Length
6	1
5	2
4	3
3	4

Final answer:

4

Example 3

Input:

[
  [1]
]

Only one cell exists.

DFS immediately returns:

1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m*n)	Each cell is computed once
Space	O(m*n)	Memo table plus recursion stack

The DFS function is called many times, but each cell's result is computed only once because of memoization. Every edge between neighboring cells is examined at most once during computation.

The recursion depth can reach m*n in the worst case if the matrix forms one long increasing chain, which contributes to auxiliary stack usage.

Test Cases

from typing import List

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

        memo = [[0] * cols for _ in range(rows)]

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]

        def dfs(row: int, col: int) -> int:
            if memo[row][col]:
                return memo[row][col]

            longest = 1

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and matrix[nr][nc] > matrix[row][col]
                ):
                    longest = max(longest, 1 + dfs(nr, nc))

            memo[row][col] = longest
            return longest

        answer = 0

        for r in range(rows):
            for c in range(cols):
                answer = max(answer, dfs(r, c))

        return answer

solution = Solution()

assert solution.longestIncreasingPath(
    [[9,9,4],[6,6,8],[2,1,1]]
) == 4  # Provided example 1

assert solution.longestIncreasingPath(
    [[3,4,5],[3,2,6],[2,2,1]]
) == 4  # Provided example 2

assert solution.longestIncreasingPath(
    [[1]]
) == 1  # Single cell matrix

assert solution.longestIncreasingPath(
    [[7,7,7],[7,7,7]]
) == 1  # All values identical

assert solution.longestIncreasingPath(
    [[5,4,3],[2,1,0]]
) == 6  # Entire matrix forms increasing chain

assert solution.longestIncreasingPath(
    [[1,2],[4,3]]
) == 4  # Spiral increasing path

assert solution.longestIncreasingPath(
    [[1,2,3],[6,5,4]]
) == 6  # Long snake-shaped path

assert solution.longestIncreasingPath(
    [[1,1,1],[1,2,1],[1,1,1]]
) == 2  # Single increasing move only

assert solution.longestIncreasingPath(
    [[0]]
) == 1  # Minimum possible value

assert solution.longestIncreasingPath(
    [[1],[2],[3],[4]]
) == 4  # Single-column increasing matrix

Test	Why
[[9,9,4],[6,6,8],[2,1,1]]	Validates standard branching case
[[3,4,5],[3,2,6],[2,2,1]]	Tests directional movement restrictions
[[1]]	Smallest possible input
[[7,7,7],[7,7,7]]	Ensures equal values do not count
[[5,4,3],[2,1,0]]	Tests long connected path
[[1,2],[4,3]]	Tests non-linear traversal
[[1,2,3],[6,5,4]]	Tests snake-like ordering
[[1,1,1],[1,2,1],[1,1,1]]	Tests isolated peak
[[0]]	Tests minimum numeric value
[[1],[2],[3],[4]]	Tests vertical traversal

Edge Cases

Single Cell Matrix

A matrix containing only one element is the smallest valid input. A naive implementation might accidentally return 0 if it assumes at least one move is required.

The implementation correctly initializes every path length as 1, meaning a single cell alone forms a valid path.

All Values Equal

If every cell contains the same value, no increasing move is possible because moves require strictly larger values.

This case is easy to mishandle if the condition uses >= instead of >.

The implementation explicitly checks:

matrix[new_row][new_col] > matrix[row][col]

so equal values are never traversed.

Large Overlapping Subproblems

In large matrices, many paths may converge into the same region. Without memoization, the same DFS computations would repeat exponentially many times.

For example, several neighboring cells may all eventually lead into the same increasing chain. Memoization guarantees that once a cell's longest path is computed, it is reused everywhere else.

This optimization is what reduces the complexity from exponential time to linear time relative to the number of cells.