Skip to main content

329 - Longest Increasing Path in a Matrix

Difficulty: Hard | Pattern: DFS + Memoization | Company tags: Amazon, Google, Uber

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.

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: [3,4,5,6] going right then down.

Approach: DFS + Memoization — O(m×n)​

Key insight: For each cell, DFS to find the longest increasing path starting there. Cache results (memo[r][c]). Since paths are strictly increasing, there are no cycles — each cell's result only depends on cells with strictly greater values.

def longestIncreasingPath(matrix: list[list[int]]) -> int:
    m, n = len(matrix), len(matrix[0])
    memo = {}
    
    def dfs(r, c):
        if (r, c) in memo:
            return memo[(r, c)]
        best = 1
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        memo[(r, c)] = best
        return best
    
    return max(dfs(r, c) for r in range(m) for c in range(n))

Dry Run​

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

Starting from cell (2,1) value=1:

  • Can go to (2,0)=2 (1→2) → from 2: can go to (1,0)=6 (2→6) → from 6: can go to (0,0)=9 (6→9)
  • Path: 1→2→6→9, length = 4

Starting from each cell and taking max gives 4 ✓

Why No Cycles?​

Each step requires strictly increasing values. Since values are finite and strictly increasing along any path, the recursion always terminates.

Complexity​

  • Time: O(m×n) — each cell computed once and cached
  • Space: O(m×n) for memo + O(m×n) recursion stack