Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Longest Increasing Path in a Matrix (LC 329)

Problem Statement

Given an m x n integer matrix, return the length of the longest strictly increasing path. You can move up, down, left, or right (not diagonally) and cannot revisit cells.

Example 1:

Input:
9 9 4
6 6 8
2 1 1
Output: 4
Explanation: 1 -> 2 -> 6 -> 9.

Example 2:

Input:
3 4 5
3 2 6
2 2 1
Output: 4
Explanation: 3 -> 4 -> 5 -> 6.

Constraints:

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

Difficulty: Hard

---

Pattern Recognition

• Input structure: 2D grid of integers.
• What are we optimizing? length of longest monotonically increasing path.
• Pattern: DFS with memoization (top-down DP) on a DAG.
• Why: the strict inequality gives you a DAG — edges go from smaller to strictly larger values, so there are no cycles and you can memoize. Each cell's longest path depends only on its larger neighbors.

Alternative: topological sort + DP. Both are O(m * n); DFS+memo is more common in interviews.

---

Approach

Brute Force — Plain DFS

From each cell, DFS outward, tracking the current path length; take max. Without memo, exponential.

Optimal — DFS + Memoization

Key Insight: longest[i][j] = length of the longest increasing path starting at (i, j). This depends only on strictly larger neighbors, which never form a cycle. Memoize to visit each cell exactly once.

memo[m][n] = 0

def dfs(i, j):
    if memo[i][j] > 0: return memo[i][j]
    best = 1
    for (ni, nj) in 4 neighbors:
        if in bounds and matrix[ni][nj] > matrix[i][j]:
            best = max(best, 1 + dfs(ni, nj))
    memo[i][j] = best
    return best

ans = 0
for each cell (i, j):
    ans = max(ans, dfs(i, j))

Time: O(m * n) — each cell computed once, constant work per cell. Space: O(m * n) for memo + recursion stack.

Alternative — Kahn's Topological Sort

Treat the grid as a DAG with edges from smaller to larger. In-degree = number of smaller neighbors. BFS by levels; longest chain = number of levels. Avoids recursion entirely — useful for gigantic grids where stack depth matters.

---

Walkthrough

Matrix:

9 9 4
6 6 8
2 1 1

DFS starts from (2,1) (value 1):

• dfs(2,1) value 1. Larger neighbors: (1,1)=6, (2,0)=2, (2,2)=1 (not strictly larger, skip).
  • dfs(1,1) value 6. Larger neighbors: (0,1)=9, (1,2)=8.
    • dfs(0,1) value 9. Larger neighbors: none. Return 1.
    • dfs(1,2) value 8. Larger neighbors: (0,2)=4? no. Return 1.
    • dfs(1,1) = 1 + max(1, 1) = 2.
  • dfs(2,0) value 2. Larger neighbors: (1,0)=6.
    • dfs(1,0) value 6. Larger neighbors: (0,0)=9. dfs(0,0)=1. Return 2.
    • dfs(2,0) = 1 + 2 = 3.
  • dfs(2,1) = 1 + max(2, 3) = 4. Matches expected.

All other cells will hit memoized values for any overlap.

---

Implementation

TypeScript

function longestIncreasingPath(matrix: number[][]): number {
    const m = matrix.length;
    const n = matrix[0].length;
    const memo: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    const dfs = (i: number, j: number): number => {
        if (memo[i][j] > 0) return memo[i][j];
        let best = 1;
        for (const [di, dj] of dirs) {
            const ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
                best = Math.max(best, 1 + dfs(ni, nj));
            }
        }
        memo[i][j] = best;
        return best;
    };

    let ans = 0;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            ans = Math.max(ans, dfs(i, j));
    return ans;
}

C++

class Solution {
    int m, n;
    vector<vector<int>> memo;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    int dfs(vector<vector<int>>& matrix, int i, int j) {
        if (memo[i][j] > 0) return memo[i][j];
        int best = 1;
        for (auto& d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
                best = max(best, 1 + dfs(matrix, ni, nj));
            }
        }
        return memo[i][j] = best;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(); n = matrix[0].size();
        memo.assign(m, vector<int>(n, 0));
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                ans = max(ans, dfs(matrix, i, j));
        return ans;
    }
};

Watch out:

1. Forgetting strict inequality (> instead of >=) introduces cycles — the memoization breaks. Always strict.
2. No need for a visited set: the strict-increase rule already prevents revisits.
3. Deep grids can overflow recursion. If interviewer pushes on stack safety, switch to Kahn's topological-sort BFS version.

---

Complexity Analysis

	Time	Space
Plain DFS	exponential	O(m * n) stack
DFS + Memo	O(m * n)	O(m * n)
Topo Sort BFS	O(m * n)	O(m * n)

Bottleneck: each cell is computed once, constant neighbors, so linear in cells.

---

Edge Cases

1. 1x1 matrix — answer 1.
2. All equal values — no strict-increase edges; answer 1.
3. Monotonically increasing row — answer = n.
4. Sparse plateaus with a single peak — memoization still handles correctly.
5. Max-size 200x200 grid — up to 40,000 cells, O(m*n) = 160,000 neighbor checks; recursion depth up to ~40,000 in worst case. Prefer Kahn's for safety.
6. Very large integer values — comparisons still work; no overflow.

---

Related Problems

• LC 174 — Dungeon Game — Grid DP with reverse traversal; same "memo on cell" pattern.
• LC 1219 — Path with Maximum Gold — Grid DFS but path constraints are different (visit-once, not monotone).
• LC 1306 — Jump Game III — DFS/BFS with memoization on a 1D implicit graph.
• LC 2328 — Number of Increasing Paths in a Grid — Count paths instead of finding the longest; same DFS structure.

---

What Is Expected at Each Level

Junior: Recognize grid DFS. Implement with memoization given a nudge. State O(m * n) complexity.

Mid-level: Write memoized DFS cleanly on first try, articulate why strict increase makes the graph a DAG, handle edge cases without prompting.

Senior (L4 target): Offer both DFS+memo and Kahn's-topological-sort BFS. Discuss stack overflow risks on 200x200 grids. Pivot comfortably to LC 2328 (counting) and discuss when to pre-sort cells by value vs DFS.