Longest Increasing Path in a Matrix

GraphsDFSMemoization

35 min

Problem Statement

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

Example 1:

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9].

Solution

This problem can be modeled as finding the longest path in a Directed Acyclic Graph (DAG), where the cells are nodes and an edge exists from cell A to B if B is adjacent to A and has a greater value.

A brute-force DFS from every cell would be too slow due to recomputing the same paths. We can optimize this by using memoization (a form of dynamic programming) to cache the results. We'll use a cache grid to store the length of the longest increasing path starting from each cell.

Algorithm Steps (DFS + Memoization)

Initialize a `cache` grid of the same size as the matrix to store computed path lengths.
Iterate through each cell `(r, c)` of the matrix.
For each cell, perform a DFS to find the longest increasing path starting from it.
The DFS function will:
Check the cache first. If the result for `(r, c)` is already computed, return it.
Explore all 4 neighbors. If a neighbor is valid and has a strictly greater value, recursively call DFS on it.
The longest path from `(r, c)` is 1 + the maximum path length from its valid neighbors.
Store this result in `cache[r][c]` before returning.
Keep track of the overall maximum path length found from all starting cells.

Longest Increasing Path

Max Length Found: 0

Progress1 / 1

Ready to start.

Longest Increasing Path (DFS + Memoization)


class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        if not matrix:
            return 0
        
        rows, cols = len(matrix), len(matrix[0])
        cache = {}  # (r, c) -> LIP

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

            res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
            cache[(r, c)] = res
            return res

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