329. Longest Increasing Path in a Matrix

Array Depth-First Search Breadth-First Search Dynamic Programming Topological Sort Memoization Matrix

Intuition

DFS with memoization on each cell: memo[i][j] = length of longest increasing path starting at (i,j). Explore all 4 directions, only moving to strictly larger values.

Algorithm

1memo[m][n] = 0 (uncomputed).
2DFS(i,j): if memo[i][j] != 0, return it.
3For each neighbor (ni,nj): if matrix[ni][nj] > matrix[i][j], best = max(best, DFS(ni,nj)+1).
4memo[i][j] = best. Return.
5Answer = max DFS(i,j) over all cells.

Example Walkthrough

Input: [[9,9,4],[6,6,8],[2,1,1]]

1.DFS(2,0)=2 -> 2->6 path. DFS(2,1)=3 -> 1->6->9. Best=4 (1->2->6->9).

Output: 4

Common Pitfalls

•Memoize to avoid exponential recomputation - each cell is computed at most once.

329.cs

// Approach: DFS with memoization — for each cell, recursively explore all four neighbors
// that have a strictly larger value, caching the longest path from each cell.
// Start a DFS from every unvisited cell; the global maximum over all starts is the answer.
// Because the path must strictly increase, no cycle is possible — no visited set is needed.
// The memoization table ensures each cell is fully computed only once.
// Time: O(m x n) — each cell visited once. Space: O(m x n) for the memo table.

public class Solution
{
    public int LongestIncreasingPath(int[][] matrix)
    {
        int m = matrix.Length;
        int n = matrix[0].Length;
        int ans = 0;
        // mem[i][j] := the LIP starting from matrix[i][j]
        int[][] mem = new int[m][];

        for (int i = 0; i < m; ++i)
            mem[i] = new int[n];

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
                ans = Math.Max(ans, Dfs(matrix, i, j, int.MinValue, mem));
        }

        return ans;
    }

    private int Dfs(int[][] matrix, int i, int j, int prev, int[][] mem)
    {
        if (i < 0 || i == matrix.Length || j < 0 || j == matrix[0].Length)
            return 0;

        if (matrix[i][j] <= prev)
            return 0;

        if (mem[i][j] > 0)
            return mem[i][j];

        int curr = matrix[i][j];
        int a = Dfs(matrix, i + 1, j, curr, mem);
        int b = Dfs(matrix, i - 1, j, curr, mem);
        int c = Dfs(matrix, i, j + 1, curr, mem);
        int d = Dfs(matrix, i, j - 1, curr, mem);
        
        return mem[i][j] = 1 + Math.Max(Math.Max(a, b), Math.Max(c, d));
    }
}

Was this solution helpful?