Compute longest rising path in a grid

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.

Longest Increasing Path in a Grid

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.

Hints

1. 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.
2. 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).
3. 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.
4. 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.