280. Longest Increasing Path in a Matrix
You receive a 2-D integer grid matrix with m rows and n columns. Starting from any cell you like, you may repeatedly step to an up/down/left/right neighbor whose value is strictly greater than the value you are standing on — no diagonal moves and no wrapping around the edges. Return the number of cells in the longest such strictly increasing path.
A path may begin and end anywhere, and a single cell on its own counts as a path of length 1, so the answer is always at least 1.
Example 1:
Input: matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
Output: 4
Explanation: The best route is 1 → 2 → 6 → 9: start at the middle of the bottom row, step left, then climb up the first column. Four cells, each strictly larger than the last.
Example 2:
Input: matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
Output: 4
Explanation: 3 → 4 → 5 → 6 walks along the top row and drops into the 6. Diagonal moves are forbidden, so nothing longer exists.
Constraints:
- 1 ≤ m, n ≤ 200
- 0 ≤ matrix[i][j] ≤ 10⁹
- Moves are up/down/left/right only, and each step must go to a strictly greater value.
Hints:
Treat the grid as a directed graph: draw an edge from each cell to every neighbor with a strictly larger value. Since values strictly increase along every edge, can this graph ever contain a cycle?
Define f(r, c) = length of the longest increasing path that starts at (r, c). Then f(r, c) = 1 + max f over the strictly larger neighbors — it depends only on cells with bigger values.
Plain DFS recomputes f for the same cell over and over, exponentially. Cache f in an m×n memo table: each cell is solved exactly once and the whole thing collapses to O(m·n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
Expected output: 4