Compute longest rising path in a grid
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates mastery of graph traversal, dynamic programming, and complexity analysis for computing longest increasing paths in a matrix, focusing on algorithmic correctness and efficient use of time and space.
Constraints
- 0 <= m, n <= 200
- Cell values fit in a 32-bit signed integer (negatives allowed).
- Moves are only up/down/left/right to a STRICTLY larger value.
- A single cell is a valid path of length 1; an empty grid returns 0.
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).
Input: ([[1]],)
Expected Output: 1
Explanation: A single cell is a path of length 1.
Input: ([],)
Expected Output: 0
Explanation: An empty grid has no cells, so the answer is 0.
Input: ([[7,7,7],[7,7,7]],)
Expected Output: 1
Explanation: All values equal — no strictly-larger neighbor exists, so every path has length 1.
Input: ([[1,2,3,4,5]],)
Expected Output: 5
Explanation: A strictly increasing row of 5 cells gives a path of length 5.
Input: ([[5],[4],[3],[2],[1]],)
Expected Output: 5
Explanation: Reading the column upward, 1 → 2 → 3 → 4 → 5 forms a path of length 5.
Input: ([[1,2],[3,4]],)
Expected Output: 3
Explanation: 1 → 2 → 4 (or 1 → 3 → 4) gives the longest path of length 3.
Hints
- The 'strictly larger' rule means the path can never form a cycle, so the grid is implicitly a DAG — you can safely memoize the longest path starting at each cell without a visited set.
- Define f(r,c) = length of the longest increasing path starting at (r,c) = 1 + max(f(neighbor)) over neighbors with a strictly greater value. Cache f to make it O(mn).
- For an iterative O(mn) version, sort cells by value (or process them in topological order using out-degrees toward larger neighbors) so each cell is finalized after the larger cells it depends on.
- Follow-ups: for huge grids convert the recursion to the iterative/topological version to dodge recursion-depth limits; for non-decreasing steps the relation can create cycles, so you must group equal-value cells (e.g. union-find / level sets); diagonal moves just add four more direction offsets.