Longest Increasing Path In a Matrix

Problem

Given an m x n integer matrix, return the length of the longest strictly increasing path, moving only up, down, left, or right at each step (no wraparound).

Examples

Example 1

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

Output:4

The path 1 -> 2 -> 6 -> 9 has length 4.

Constraints

1 <= m, n <= 200

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the 2-D Dynamic Programming pattern

The same DP idea as 1-D, but the state depends on two indices — often two positions in a grid, or a position in each of two sequences being compared.

Look for this pattern when

You're comparing two sequences (finding a longest common subsequence, edit distance).
You're computing paths or optimal values across a 2-D grid.

Read the full 2-D Dynamic Programming guide →

Video walkthroughs

Original problem on LeetCode ↗