Longest Uphill Walk

Hard

You are given a height map heights, a rectangular table with m rows and n columns. A hiker may start in any cell and in one step move to a cell sharing a side with the current one (up, down, left or right; no diagonals, no wrapping around the edges), but only if that cell is strictly higher. Return the largest number of cells such a walk can visit, counting the starting cell.

Example 1

heights=[[3, 4, 5], [2, 9, 6], [1, 8, 7]] → 9

The walk 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 spirals through the whole grid.

Example 2

heights=[[5, 5], [5, 5]] → 1

There is nowhere to climb: neighbours have the same height and each step must go strictly up. A single cell is a walk of length 1.

Example 3

heights=[[1, 7, 2, 8]] → 2

Constraints

1 ≤ m, n ≤ 200
0 ≤ heights[i][j] ≤ 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort Memoization Array Dynamic Programming Matrix

Similar problems

Uphill-Only Walks Hard Mouse, Cat and Cheese Hard Letter Order From a Dictionary Hard Ball Into the Hole Hard Six-Cell Tile Slider Hard

Input

heights=[[3, 4, 5], [2, 9, 6], [1, 8, 7]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.