Longest Increasing Path In a Matrix

Hard · 2-D Dynamic Programming

You are given a rectangular grid of non-negative integers. Starting from any cell, you may repeatedly step to a vertically or horizontally adjacent cell whose value is strictly greater than the current cell's value; diagonal moves are not allowed. Find the length, in number of cells, of the longest such strictly increasing path anywhere in the grid, and return that length.

Examples

Input:  matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Why:    The path 1 -> 2 -> 6 -> 9 moves through adjacent cells with strictly increasing values, and no longer such path exists.

Input:  matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Why:    The path 3 -> 4 -> 5 -> 6 gives length 4, which is the longest strictly increasing chain of adjacent cells.

Input:  matrix = [[1]]
Output: 1
Why:    A single cell forms a path of length 1 by itself.

Constraints

1 <= matrix.length, matrix[0].length <= 200, 0 <= matrix[i][j] <= 2^31 - 1

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Longest Increasing Path In a Matrix

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Longest Increasing Path In a Matrix. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.