All problems

Longest Increasing Path in a Matrix

Hard · dynamic programming

A hiker is studying a rectangular map. heights[r][c] is the height of the square in row r and column c.

From any square the hiker can step to the square directly above, below, left or right of it (never diagonally, and never off the map), but only if that square is strictly higher than the one they are standing on. Equal heights and lower heights are not allowed.

The hiker may begin on any square. Return the largest number of squares they can visit in one walk, counting the starting square.

Examples

Example 1

Input: heights = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]

Output: 4

Start on the 3 in the top-left corner and walk 3, 4, 5, 6. No walk visits more squares.

Example 2

Input: heights = [[7, 7], [7, 7]]

Output: 1

Every neighbour has the same height, so the hiker cannot move at all.

Example 3

Input: heights = [[1, 2, 3], [6, 5, 4]]

Output: 6

Walk along the top row, then back along the bottom row: 1, 2, 3, 4, 5, 6.

Constraints