Return the length of the longest path in the matrix where each step moves to an adjacent cell (up, down, left, right) with a strictly larger value.
Before you code
The longest path starting at a cell is the same no matter how you reached it, and strictly increasing paths can't loop. So the answer for each cell can be computed once and reused.
Hints
longest(r, c) = 1 + max(longest(nr, nc))over neighbors with larger values, or 1 if none.- Memoize on (r, c). Each cell is computed once: O(R × C).
- No visited set is needed: increasing values rule out cycles.
Production & complexity notes
When solving Longest increasing path in a matrix on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Memoization to reinforce the underlying pattern.
What it practices
Memoizing a search on a directed acyclic graph, from Memoization.