Longest Increasing Path in a Matrix

Hard

Description

A hiking map is a grid of numbers called matrix. Each number is the height of that spot.

You can start at any spot. From a spot you may step up, down, left or right, but not diagonally, and you cannot leave the grid. Every step must go to a strictly higher spot.

Return the number of spots on the longest uphill path you can walk.

Examples

Example 1:

Input: matrix = [[1,2,3],[6,5,4]]
Output: 6
Explanation: The path 1, 2, 3, 4, 5, 6 goes around the grid and has 6 spots.

Example 2:

Input: matrix = [[7,7],[7,7]]
Output: 1
Explanation: All heights are equal, so you cannot take any step. The best path is one spot.

Example 3:

Input: matrix = [[3,6,9],[2,5,8],[1,4,7]]
Output: 5
Explanation: The longest path is 1, 2, 3, 6, 9, which has 5 spots.

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

Constraints

0 <= matrix[i][j] <= 2147483647
1 <= matrix.length <= 200
1 <= matrix[i].length <= 200
All rows of matrix have the same length.

Examples

3 shown

Example 1

Input

[[1,2,3],[6,5,4]]

Output

Example 2

Input

[[7,7],[7,7]]

Output

Example 3

Input

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

Output

Opening the editor...