329. Longest Increasing Path in a Matrix

Problem¶

Given an integer matrix, return the maximum number of cells in a path where:

Each move is up, down, left, or right.
Every next value is strictly larger.
The path remains inside the matrix.

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

path: 1 -> 2 -> 6 -> 9
output: 4

Key trick¶

Treat each cell as a node in a directed acyclic graph, with edges from smaller values to larger adjacent values. Kahn's topological sort processes this graph in layers, and the number of layers is the longest increasing path.

Trap¶

Exploring every possible path without caching repeats the same work exponentially.
Equal values are not increasing.
A recursive memoized DFS may exceed Python's recursion limit because a path can contain up to \(mn\) cells.
A visited set is unnecessary because strictly increasing edges cannot form a cycle.

Why is it interesting?¶

It converts a matrix search problem into longest-path computation on an implicit DAG, which can be solved in linear time without recursion.

Python solution¶

from collections import deque


class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        indegree = [[0] * n for _ in range(m)]
        directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

        # Count each cell's adjacent predecessors with smaller values.
        for r in range(m):
            for c in range(n):
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (
                        0 <= nr < m
                        and 0 <= nc < n
                        and matrix[nr][nc] < matrix[r][c]
                    ):
                        indegree[r][c] += 1

        # Local minima have no smaller predecessor.
        q = deque(
            (r, c)
            for r in range(m)
            for c in range(n)
            if indegree[r][c] == 0
        )

        length = 0

        # Each topological layer adds one cell to the longest path.
        while q:
            length += 1

            for _ in range(len(q)):
                r, c = q.popleft()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (
                        0 <= nr < m
                        and 0 <= nc < n
                        and matrix[nr][nc] > matrix[r][c]
                    ):
                        indegree[nr][nc] -= 1

                        if indegree[nr][nc] == 0:
                            q.append((nr, nc))

        return length

Time complexity: \(O(mn)\).

Space complexity: \(O(mn)\).

Comment on my solution¶

Your backtracking is logically close, but it recomputes paths from the same cells many times, causing exponential worst-case time and the timeout.

Strictly increasing movement already prevents cycles, so replacing cells with "#" is unnecessary.
Mutating an integer matrix with a string temporarily mixes types and complicates the search.
Keeping the entire path is unnecessary when only its length matters.
Calling DFS on invalid or non-increasing neighbors adds avoidable work.
Memoizing the best path starting at each cell would reduce the time to \(O(mn)\), but recursive depth remains a Python concern for very long paths.

# WRONG
# Time Limit Exceeded: 135/139 testcases passed
class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        # [[9,9,4],
        #  [6,6,8],  -> [1, 2, 6, 9] -> 4
        #  [2,1,1]]

        m, n = len(matrix), len(matrix[0])
        best = 0
        path = []

        def dfs(r, c):
            nonlocal best
            if r < 0 or r >= m or c < 0 or c >= n or matrix[r][c] == "#":
                best = max(best, len(path))
                return

            x = matrix[r][c]

            if path and path[-1] >= x:
                best = max(best, len(path))
                return

            path.append(x)
            matrix[r][c] = "#"

            for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
                nr, nc = r + dr, c + dc
                dfs(nr,nc)

            matrix[r][c] = x
            path.pop()

        for r in range(m):
            for c in range(n):
                dfs(r,c)

        return best