DSA problem
Longest Increasing Path in a Matrix
Given an m x n integer matrix, return the length of the longest strictly increasing path. From each cell you may move to one of its four orthogonal neighbors (up, down, left, right) — diagonal moves are not allowed. You may not revisit a cell.
Because every step must strictly increase the value, the path can never enter a cycle: the natural numeric ordering forbids visiting the same cell twice along a strictly increasing trip. That insight is the key. The grid effectively becomes a DAG whose edge u -> v exists when v is a higher-valued neighbor of u. The answer is the longest path in this DAG.
A brute-force DFS from every cell, exploring all increasing paths, costs O(2^(m * n)) in the worst case. The cure is memoization: let memo[r][c] = length of the longest strictly increasing path starting at (r, c). The recurrence is memo[r][c] = 1 + max(memo[nr][nc]) over all four neighbors (nr, nc) with matrix[nr][nc] > matrix[r][c], defaulting to 0 if no such neighbor exists.
DFS with memo visits every cell's recursion exactly once, so the total work is bounded by the number of edges, which is O(m * n) (each cell has at most 4 neighbors). The maximum over all starting cells is the answer. An alternative iterative approach uses Kahn-style topological order over the DAG, but the memoized DFS is the cleanest formulation. Time O(m * n), space O(m * n) for the memo plus recursion stack.
Examples
matrix = [[9,9,4],[6,6,8],[2,1,1]]4matrix = [[3,4,5],[3,2,6],[2,2,1]]4matrix = [[1]]1Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2^31 - 1
- You may only move up, down, left, or right (no diagonals).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.