Longest Increasing Path in a Matrix

Difficulty: Hard Source: NeetCode

Problem

Given an m x n integer matrix, return the length of the longest increasing path. From each cell, you can move in 4 directions (up, down, left, right). You cannot move diagonally or outside the boundary. The path must be strictly increasing.

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS on a grid — exploring neighbours with recursion
• Memoization — caching DFS results to avoid recomputation
• Topological sort (optional) — alternative BFS-based approach

1. Brute Force / DFS Without Memoization

Intuition

From each cell, do a DFS exploring all four directions, only moving to a strictly larger neighbour. Track the length of the longest path found from this cell. Call this for every cell and return the global maximum. Without caching, we recompute the same paths many times.

Algorithm

1. For each cell (i, j), call dfs(i, j, -1) (previous value starts at -1 so any cell is valid).
2. In DFS: for each of 4 directions, if the neighbour is in bounds and strictly larger, recurse.
3. Return 1 + max(neighbour results).

Solution

def longestIncreasingPath(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def dfs(i, j, prev_val):
        if i < 0 or i >= m or j < 0 or j >= n:
            return 0
        if matrix[i][j] <= prev_val:
            return 0
        best = 1
        for di, dj in dirs:
            result = dfs(i + di, j + dj, matrix[i][j])
            best = max(best, 1 + result)
        return best

    ans = 0
    for i in range(m):
        for j in range(n):
            ans = max(ans, dfs(i, j, -1))
    return ans


print(longestIncreasingPath([[9, 9, 4], [6, 6, 8], [2, 1, 1]]))   # 4
print(longestIncreasingPath([[3, 4, 5], [3, 2, 6], [2, 2, 1]]))   # 4

Complexity

• Time: O((m*n)²) — very slow, re-explores paths
• Space: O(m*n) — recursion stack

2. DFS with Memoization

Intuition

The key observation: the longest path starting from (i, j) is always the same regardless of how we got there — because we only move to strictly larger values, there are no cycles. This means we can safely cache dp[i][j] = longest increasing path starting at (i, j). Once computed, reuse it.

Algorithm

1. Create a dp table of zeros.
2. For each cell (i, j), call dfs(i, j).
3. In dfs(i, j): if dp[i][j] is already computed, return it.
4. Otherwise, check all 4 neighbours that are in bounds and strictly greater.
5. dp[i][j] = 1 + max(dfs(neighbour)) over valid neighbours.
6. Return dp[i][j].

Solution

def longestIncreasingPath(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def dfs(i, j):
        if dp[i][j]:
            return dp[i][j]
        best = 1
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                best = max(best, 1 + dfs(ni, nj))
        dp[i][j] = best
        return best

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


print(longestIncreasingPath([[9, 9, 4], [6, 6, 8], [2, 1, 1]]))   # 4
print(longestIncreasingPath([[3, 4, 5], [3, 2, 6], [2, 2, 1]]))   # 4
print(longestIncreasingPath([[1]]))                                  # 1
print(longestIncreasingPath([[1, 2], [3, 4]]))                      # 3 (1→2→4 or 1→3→4)

Complexity

• Time: O(m * n) — each cell computed exactly once
• Space: O(m * n) — dp table + recursion stack

Common Pitfalls

Using a visited set instead of memoization. You don’t need a visited set here — the strictly increasing constraint already prevents cycles. If you add one, it will interfere with the memoization by blocking valid paths that visit a cell from a different direction.

Checking < instead of <=. The path must be strictly increasing, so matrix[ni][nj] > matrix[i][j]. Using >= would allow equal values and could create infinite loops.

Initialising dp with 0 and misreading the cache. We check if dp[i][j] to detect a cached result. Since paths have length at least 1, dp[i][j] = 0 means “not yet computed” — safe to use. If your grid had valid 0-length results, you’d need a sentinel like -1 instead.