Compute longest increasing path in a matrix
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an m × n integer matrix, return the length of the longest path of strictly increasing values, where from each cell you may move only up, down, left, or right. Design an efficient algorithm and analyze its time and space complexity. Follow-up: Handle very large matrices where recursion depth could be an issue; provide an iterative or memoized approach that avoids stack overflow.
Quick Answer: Compute longest increasing path in a matrix evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given an m x n integer matrix `matrix`, return the length of the longest path of strictly increasing values. From each cell you may move in four directions: up, down, left, or right. You may NOT move diagonally or move outside the matrix boundary. The path does not need to start or end at any particular cell, and a path of a single cell has length 1.
Design an efficient algorithm. A brute-force DFS from every cell re-explores the same sub-paths repeatedly; cache the longest increasing path starting at each cell (memoization / top-down DP) so every cell is computed once. This runs in O(m*n) time and O(m*n) space.
Follow-up: For very large matrices where recursion depth could overflow the stack, the same caching idea can be expressed iteratively by processing cells in increasing value order (or via topological order / BFS over the DAG where edges point from smaller to larger neighbors).
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
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Example 3:
Input: matrix = [[1]]
Output: 1
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2^31 - 1
Examples
Input: ([[9,9,4],[6,6,8],[2,1,1]],)
Expected Output: 4
Explanation: Longest increasing path is 1 -> 2 -> 6 -> 9 (length 4).
Input: ([[3,4,5],[3,2,6],[2,2,1]],)
Expected Output: 4
Explanation: Longest increasing path is 3 -> 4 -> 5 -> 6 (length 4); diagonal moves are not allowed.
Hints
- Brute-force DFS from every cell recomputes overlapping sub-paths. Notice that the longest increasing path starting at a given cell depends only on that cell — so it can be cached.
- Use memoization: dfs(r, c) = 1 + max(dfs(neighbor)) over the four orthogonal neighbors whose value is strictly greater than matrix[r][c]; default to 1 when no larger neighbor exists.
- Because edges only point from smaller to larger values, the cells form a DAG (no cycles), so memoization never loops. The answer is the maximum dfs value over all cells.
- Follow-up (avoid deep recursion): sort cells by value ascending and relax each cell from its already-processed smaller neighbors, or run a topological/BFS peeling of the DAG — both compute the same DP iteratively with O(1) recursion depth.