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

From each cell, you can move in four directions: up, down, left, or right. You may not move diagonally or outside the boundary.

Examples

Example 1:

Input:
  9  9  4
  6  6  8
  2  1  1

Output: 4

One longest path: 1 → 2 → 6 → 9

Example 2:

Input:
  3  4  5
  3  2  6
  2  2  1

Output: 4

One longest path: 3 → 4 → 5 → 6

Constraints

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

Thinking Process

Why Brute Force Fails

Starting DFS from every cell without caching repeats enormous amounts of work. A cell deep in the matrix gets re-explored from every path that leads to it.

DFS + Memoization

Define dp[i][j] = length of the longest increasing path starting from (i, j).

From (i, j), try all 4 neighbors (nr, nc) where matrix[nr][nc] > matrix[i][j]:

dp[i][j] = 1 + max(dp[nr][nc]) for all valid strictly-greater neighbors

If no neighbor is strictly greater, dp[i][j] = 1.

Since values are strictly increasing, there are no cycles. Each cell is computed exactly once, then cached.

Alternative: Topological Sort (BFS)

Think of the grid as a DAG: draw an edge u → v whenever matrix[v] > matrix[u]. Then the longest increasing path = longest path in this DAG, which we can find via topological sort (Kahn’s algorithm):

  1. Compute indegree of each cell (number of strictly-smaller neighbors)
  2. Start BFS from all cells with indegree 0 (local minima)
  3. Process layer by layer; each layer = one step in the path
  4. Number of BFS layers = answer

Solution 1: DFS + Memoization – $O(mn)$ time, $O(mn)$ space

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        int result = 0;

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                result = max(result, dfs(matrix, dp, i, j));
            }
        }
        return result;
    }

private:
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int r, int c) {
        if (dp[r][c] != 0) return dp[r][c];
        int rows = matrix.size();
        int cols = matrix[0].size();
        int maxLen = 1;

        for (auto& d : dirs) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                matrix[nr][nc] > matrix[r][c]) {
                maxLen = max(maxLen, 1 + dfs(matrix, dp, nr, nc));
            }
        }
        dp[r][c] = maxLen;
        return maxLen;
    }
};

Why No Visited Array?

Unlike typical grid DFS, we don’t need a visited set. The strictly increasing constraint guarantees no cycles – you can never return to a cell you’ve already visited on the current path since its value would have to be both smaller and larger.

Why Memoization Works

Once dp[r][c] is computed, every future call that reaches (r, c) returns immediately. Each cell is fully explored exactly once, so total work across all DFS calls is $O(mn)$.

Solution 2: Topological Sort (BFS) – $O(mn)$ time, $O(mn)$ space

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();

        vector<vector<int>> indegree(rows, vector<int>(cols, 0));
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                for (auto& d : dirs) {
                    int nr = r + d[0];
                    int nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                        matrix[nr][nc] < matrix[r][c]) {
                        indegree[r][c]++;
                    }
                }
            }
        }

        queue<pair<int, int>> q;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (indegree[r][c] == 0) {
                    q.push({r, c});
                }
            }
        }

        int pathLen = 0;
        while (!q.empty()) {
            int size = q.size();
            pathLen++;
            for (int i = 0; i < size; ++i) {
                auto [r, c] = q.front();
                q.pop();
                for (auto& d : dirs) {
                    int nr = r + d[0];
                    int nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                        matrix[nr][nc] > matrix[r][c]) {
                        if (--indegree[nr][nc] == 0) {
                            q.push({nr, nc});
                        }
                    }
                }
            }
        }
        return pathLen;
    }
};

Walk-through

Matrix:
  9  9  4
  6  6  8
  2  1  1

Indegree (# of strictly smaller neighbors):
  2  2  1
  1  1  2
  0  0  0

Layer 0 (indegree=0): (2,0)=2, (2,1)=1, (2,2)=1   pathLen=1
  Process: decrement neighbors' indegrees

Layer 1: (1,0)=6, (1,1)=6, (0,2)=4                  pathLen=2

Layer 2: (0,0)=9, (0,1)=9, (1,2)=8                  pathLen=3

Layer 3: (nothing new? let's trace...)
  Actually: after layer 1, (1,2)=8 gets indegree 0
  After layer 2, nothing remains

pathLen = 4  ✓

Comparison

Aspect DFS + Memoization Topological Sort (BFS)
Approach Top-down recursion with cache Bottom-up layer-by-layer
Recursion Yes (stack depth up to $mn$) No (iterative)
Space $O(mn)$ dp + recursion stack $O(mn)$ indegree + queue
When to prefer Simpler to write, natural for path problems Avoids stack overflow on large inputs
Key insight Strictly increasing = no cycles = safe to memo Grid as DAG, longest path via topo sort

Common Mistakes

  • Forgetting the strictly-greater check: Using >= instead of > creates cycles and infinite recursion
  • Using a visited array: Unnecessary here and would actually prevent correct memoization (a cell should be reachable from multiple starting points)
  • Returning 0 for base case: A single cell is a path of length 1, not 0

Key Takeaways

  • DFS + memoization on grid is a core pattern: define dp[i][j] as the answer starting from (i, j), recurse on valid neighbors, cache results
  • Strictly increasing guarantees a DAG – no cycles means memoization is safe and topological sort applies
  • The BFS approach reveals the problem’s structure: it’s just longest path in a DAG disguised as a grid problem
  • Both solutions are $O(mn)$ – choose based on whether you prefer recursive or iterative style

Template Reference