2-D Dynamic Programming Paths in a grid
540. Longest Increasing Path in a Matrix
You are given a grid of integers, matrix. A path starts at any cell and moves one step at a time to the
cell directly above, below, left or right. It cannot move diagonally or leave the grid.
A path is increasing when every cell on it holds a bigger value than the cell before it. So two cells with equal values can never be next to each other on it. Return the number of cells on the longest increasing path. A single cell is an increasing path of length 1.
Example 1
Input: matrix = [[3, 4, 5, 6], [2, 9, 8, 7], [1, 10, 5, 1]]
10Explanation: The path 1 → 2 → 3 → … → 10 goes up the left column, along the top row, down to 7, left to 9, and down to 10. It uses steps in all four directions.
Example 2
Input: matrix = [[7, 7], [7, 7]]
1Explanation: Every neighbour holds an equal value, so no path can take a step.
Example 3
Input: matrix = [[-1000000000, 5, 1000000000, 5, -3]]
3Explanation: Both -1000000000 → 5 → 1000000000 and -3 → 5 → 1000000000 have 3 cells. No path can go past the 1000000000.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == matrix.length,n == matrix[i].length1 ≤ m, n ≤ 1051 ≤ m · n ≤ 105-109 ≤ matrix[i][j] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.