Longest Uphill Trail
HardMatrix
Problem
A hiking map is an m × n grid of altitudes. A trail is a sequence of cells where each step moves to an orthogonally adjacent cell (up, down, left or right) with a strictly higher altitude.
Return the number of cells on the longest possible trail.
Example 1
- Input:
- grid = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
- Output:
- 4
One longest trail is 1 → 2 → 6 → 9.
Example 2
- Input:
- grid = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
- Output:
- 4
3 → 4 → 5 → 6. Moving between equal altitudes is not allowed.
Example 3
- Input:
- grid = [[1]]
- Output:
- 1
Constraints
- 1 ≤ m, n ≤ 200
- 0 ≤ grid[i][j] ≤ 2^31 - 1
Hint
Show the first hint
Because every step goes strictly uphill, a trail can never revisit a cell, and there are no cycles. What structure does that give you?
Walkthrough
How to approach it
01Clarify before coding
- Diagonal moves? No, only the four orthogonal directions.
- Equal altitudes? Not allowed: each step must be strictly higher.
- Is the answer counted in cells or steps? Cells, so a lone cell gives 1.
02Brute force
Run a DFS from every cell exploring every uphill path and keep the longest.
Cost: Exponential in the worst case: the same sub-trails are re-explored from every cell that can reach them.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.