Longest Increasing Path in a Matrix

Problem

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

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].

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]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

Constraints:

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

Solution

Approach: DFS with Memoization

The key insight is to use DFS from each cell to find the longest path, caching results to avoid recomputation.

Implementation

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

        m, n = len(matrix), len(matrix[0])
        memo = {}

        def dfs(r, c):
            if (r, c) in memo:
                return memo[(r, c)]

            max_length = 1  # At least the cell itself
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Check bounds and increasing condition
                if (0 <= nr < m and 0 <= nc < n and
                    matrix[nr][nc] > matrix[r][c]):
                    max_length = max(max_length, 1 + dfs(nr, nc))

            memo[(r, c)] = max_length
            return max_length

        result = 0
        for i in range(m):
            for j in range(n):
                result = max(result, dfs(i, j))

        return result

Approach 2: Topological Sort (BFS)

from collections import deque

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

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

        # Calculate in-degrees
        for i in range(m):
            for j in range(n):
                for dr, dc in directions:
                    ni, nj = i + dr, j + dc
                    if (0 <= ni < m and 0 <= nj < n and
                        matrix[ni][nj] < matrix[i][j]):
                        in_degree[i][j] += 1

        # Start with cells that have no incoming edges
        queue = deque()
        for i in range(m):
            for j in range(n):
                if in_degree[i][j] == 0:
                    queue.append((i, j))

        length = 0

        while queue:
            length += 1
            for _ in range(len(queue)):
                r, c = queue.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]):
                        in_degree[nr][nc] -= 1
                        if in_degree[nr][nc] == 0:
                            queue.append((nr, nc))

        return length

Complexity Analysis

DFS with Memoization:

Time Complexity: O(m * n), each cell is visited once and result is cached.
Space Complexity: O(m * n) for memoization and recursion stack.

Topological Sort:

Time Complexity: O(m * n), processing each cell and its neighbors.
Space Complexity: O(m * n) for in-degree array and queue.

Key Insights

DAG Structure: The increasing path constraint creates a directed acyclic graph (DAG).
No Cycles: Since paths must be strictly increasing, there can be no cycles.
Memoization: Each cell’s longest path is computed once and reused.
Four Directions: From each cell, explore all four adjacent cells that have larger values.
Global Maximum: Try starting from every cell and track the global maximum path length.
Topological Sort Interpretation: Treat smaller values as coming before larger values in topological order.