Longest Increasing Path in a Matrix
Hard · 2-D Dynamic Programming · Array · Dynamic Programming · Depth-First Search · Breadth-First Search · Graph · Topological Sort · Memoization · Matrix
Problem
Given an m × n grid of integers, return the length of the longest strictly increasing path in it.
From a cell you may step up, down, left or right, but not diagonally and not off the edge. Every step must go to a strictly larger value, so two equal neighbours never form a step. The length counts cells: a single cell is a path of length 1.
Some tests contain increasing paths thousands of cells long, which is deeper than Python’s default recursion limit of 1,000. A recursive search has to be made iterative to pass them.
Examples
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4
The path 1, 2, 6, 9 starts at the bottom middle, steps left, then up twice.
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]] Output: 4
The path 3, 4, 5, 6 runs along the top row and turns down. Moving diagonally is not allowed.
Constraints
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2^31 - 1
Approaches
- DFS with memoisation — time O(m · n), space O(m · n)
Related problems
Start free on Cariara · Coding problems · System design studio
