Longest Increasing Path in a Matrix

The key idea

Every cell's answer — the longest increasing path that STARTS at that cell — depends only on its four neighbors that are strictly larger. That makes the subproblem acyclic (values strictly increase along any path), so there are no cycles to worry about. Memoize the longest path starting from each cell and each cell is solved exactly once.

Problem

Given an m x n integers matrix, return the length of the longest strictly increasing path in matrix.

From each cell, you can move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (that is, wrapping around is not allowed).

A path is strictly increasing when each cell you move to holds a value strictly greater than the cell you came from. The path length is the number of cells it visits, and a single cell counts as a path of length 1.

Constraints

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

Examples

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]] Output: 4

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

Input: matrix = [[1]] Output: 1

Complexity

Time: O(m*n) Space: O(m*n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →