Longest Increasing Path in a Matrix
Part of Practice: Prefix & Memo DP
Given an m x n grid of integers, find the length of the longest path whose values are strictly increasing. From any cell you may step up, down, left, or right (no diagonals, no wrapping), and each step must move to a strictly larger value. The path length is the number of cells visited.
Constraints: 1 <= m, n <= 200 and cell values fit in a 32-bit integer.
Examples
- Input:
- matrix = [[9,9,4],[6,6,8],[2,1,1]]
- Output:
- 4
The longest increasing path is 1 -> 2 -> 6 -> 9.
- Input:
- matrix = [[3,4,5],[3,2,6],[2,2,1]]
- Output:
- 4
The longest increasing path is 3 -> 4 -> 5 -> 6. Diagonal moves are not allowed.
- Input:
- matrix = [[1]]
- Output:
- 1
A single cell is a path of length 1.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.