Longest Increasing Path in a Matrix
Real-world version: Tallest Stack AscentThe statement here is our own: the same inputs, outputs and technique.
A container yard is laid out as a rectangular grid of bays. heights[r][c] is how many containers are stacked in the bay at row r, column c.
A gantry inspector walks the yard bay by bay. From a bay the inspector may step to a bay sharing an edge with it, up, down, left or right, and only if that bay's stack is strictly taller than the one just left. Diagonal steps are not possible, and the walk may not leave the yard.
The inspector picks the starting bay. Return the greatest number of bays a single walk can cover, counting the starting bay itself.
Examples
Example 1
- Input
- heights = [[1, 5, 9], [2, 4, 8], [3, 7, 6]]
- Output
- 5
Starting at the bay holding 1 the inspector can reach 2, then 4, then 5, then 9, covering five bays. No walk covers six.
Example 2
- Input
- heights = [[4, 4], [4, 4]]
- Output
- 1
Every stack is the same height, so no step is ever allowed and the walk is the starting bay on its own.
Example 3
- Input
- heights = [[2, 3, 6], [5, 4, 7]]
- Output
- 4
From 2 the inspector goes to 3, then down to 4, then left to 5, covering four bays. The route through 6 and 7 also stops at four.
Constraints
- rows == heights.length
- cols == heights[r].length
- 1 <= rows, cols <= 200
- 0 <= heights[r][c] <= 2^31 - 1
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def longest_ascent(heights: list[list[int]]) -> int:public int longestAscent(int[][] heights)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's