Compute longest rising path in a grid
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an m×n grid of integers, find the length of the longest path where each step moves up, down, left, or right to a strictly larger value. Return the maximum length over all starting cells. Design an O(mn) solution using memoized DFS or an equivalent iterative/topological approach, and analyze time and space usage. As a follow-up, discuss handling very large grids, recursion-depth limits, and variants such as allowing non-decreasing steps or diagonal moves.
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.
Given an m×n grid of integers, find the length of the longest path where each step moves up, down, left, or right to a strictly larger value. Return the maximum length over all starting cells. Diagonal moves and wrap-around are not allowed, and you may not revisit a cell within a path.
Design an O(mn) solution using memoized DFS (or an equivalent topological/iterative approach) and analyze its time and space usage.
Example:
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Answer = 4, via the path 1 → 2 → 6 → 9.
The path length is the number of cells visited (a single cell counts as length 1). For an empty grid, return 0.
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).
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.