Frequently Asked at Uber — This problem has been reported multiple times in recent Uber L5A interviews.

Longest Increasing Path in a Matrix

Problem Statement

Given an m x n integer matrix, find the length of the longest strictly increasing path. You may move up, down, left, or right one cell at a time, but every move must go to a strictly larger value.

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

• What is the structure of the input? A 2D grid. Treat it as an implicit graph where edges point from smaller to larger neighbors.
• What are we optimizing? Longest path in that graph.
• What pattern does this suggest? DFS with memoization — equivalently, DP on a DAG.
• Why does this pattern fit? Since every edge goes from a smaller value to a larger one, the graph has no cycles — it's a DAG. "Longest path in a DAG" is a classic memoized-DFS problem.

---

Approach

Brute Force — Plain DFS from every cell

From each cell, explore all four directions recursively, summing up 1 plus the best child.

Time: O(4^(mn)) in the worst case — you branch into 4 neighbors at every step. Space: O(mn) recursion depth. Why insufficient: Exponential. Even a 10x10 grid will TLE.

Optimal — DFS + Memoization

Key Insight: dfs(r, c) = 1 + max(dfs(neighbors with strictly larger values)). Because values strictly increase along any path, no cell is ever reached by a cycle — so memoizing the result for each cell is always correct.

Step-by-step:

1. Initialize a memo table memo[r][c] of zeros.
2. Define dfs(r, c):
   • If memo[r][c] is non-zero, return it.
   • Start with best = 1 (the cell itself).
   • For each neighbor with matrix[nr][nc] > matrix[r][c], update best = max(best, 1 + dfs(nr, nc)).
   • Cache and return.
3. Call dfs from every cell and take the global max.

Time: O(m * n) — each cell's memo is computed exactly once, and each computation inspects 4 neighbors. Space: O(m * n) for memo plus recursion stack.

---

Walkthrough

Matrix:

9 9 4
6 6 8
2 1 1

We evaluate dfs(r, c) for each cell. Since values are strict, many calls hit the base case immediately.

Cell	Value	Reasoning	Memo
(0,0)	9	no larger neighbor	1
(0,1)	9	no larger neighbor	1
(0,2)	4	neighbor 8 -> dfs(1,2)=2	1 + 2 = 3
(1,0)	6	neighbor 9 -> dfs(0,0)=1	1 + 1 = 2
(1,1)	6	neighbor 9 -> 1, neighbor 8 -> 2	1 + 2 = 3
(1,2)	8	neighbor 9 -> 1	1 + 1 = 2
(2,0)	2	neighbor 6 -> 2	1 + 2 = 3
(2,1)	1	neighbor 2 -> 3, neighbor 6 -> 3	1 + 3 = 4
(2,2)	1	neighbor 8 -> 2	1 + 2 = 3

Global max = 4, starting from (2,1) with path 1 -> 2 -> 6 -> 9.

---

Implementation

TypeScript

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

  const dfs = (r: number, c: number): number => {
    if (memo[r][c]) return memo[r][c];
    let best = 1;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && matrix[nr][nc] > matrix[r][c]) {
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }
    memo[r][c] = best;
    return best;
  };

  let result = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      result = Math.max(result, dfs(r, c));
  return result;
}

C++

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> memo(rows, vector<int>(cols, 0));
        vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        function<int(int,int)> dfs = [&](int r, int c) {
            if (memo[r][c]) return memo[r][c];
            int best = 1;
            for (auto [dr, dc] : dirs) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && matrix[nr][nc] > matrix[r][c])
                    best = max(best, 1 + dfs(nr, nc));
            }
            return memo[r][c] = best;
        };
        int result = 0;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                result = max(result, dfs(r, c));
        return result;
    }
};

Watch out: Forgetting the strict inequality matrix[nr][nc] > matrix[r][c]. Allowing equality re-introduces cycles and breaks memoization.

Watch out: Base case of 1 — the cell itself counts as length 1. Starting at 0 will always give an off-by-one.

Watch out: On 200x200 the recursion depth can hit 40000 in theory. In JS this may blow the stack; mention the iterative topological-sort-by-value variant if asked.

---

Complexity Analysis

	Time	Space
Brute Force DFS	O(4^(m*n))	O(m*n)
DFS + Memo	O(m*n)	O(m*n)

Bottleneck: Each cell's memo is computed once, with O(1) work per computation (four neighbors).

---

Edge Cases

1. 1x1 matrix — Answer is 1.
2. All equal values — No edges; answer is 1.
3. Monotonic row — Answer is the row length.
4. Monotonic spiral — Answer equals total cells; stack depth can be full m * n.
5. Very large values — Values fit in int; the comparison is plain integer compare.

---

Related Problems

• LC 62 — Unique Paths: Count paths in a DAG with right/down edges.
• LC 1048 — Longest String Chain: Longest path in a DAG induced by predecessor relation.
• LC 300 — Longest Increasing Subsequence: Same "longest chain under <" idea, 1D.
• LC 2328 — Number of Increasing Paths in a Grid: Same DAG, count instead of length.

---

What Is Expected at Each Level?

Junior / New Grad: Recognize DFS. Should arrive at memoization with a nudge once they see repeated work. Explain why cycles are impossible.

Mid-level: Immediately write memoized DFS, state O(m*n), and discuss why strict increase guarantees a DAG. Handle edge cases without prompting.

Senior: Offer the iterative alternative — topological sort by value (sort all cells, process smallest to largest, update neighbors). Discuss stack-depth concerns in languages without TCO, and generalize to "longest path with weighted edges" variants.