Longest increasing path in a grid

hardDynamic programming, 2DDepth-first searchRecursion target 40 min

Longest increasing path in a grid

Not solved yetLeetCode 329. Longest Increasing Path in a Matrix

You get a grid of integers matrix with m rows and n columns. A path starts at any cell and moves one step at a time up, down, left or right: never diagonally, and never off the grid. A path is increasing when every cell on it holds a bigger number than the cell before it.

Return the number of cells on the longest increasing path.

Example 1

Inputmatrix = [[3, 4, 5], [2, 7, 6]]Output6

2, 3, 4, 5, 6, 7: up from the 2, right along the top row, down to the 6, then left to the 7.

Example 2

Inputmatrix = [[5, 5], [5, 5]]Output1

Equal numbers do not increase, so every increasing path is a single cell.

Example 3

Inputmatrix = [[1, 2, 3], [6, 5, 4], [7, 8, 9]]Output9

The path snakes through every cell: along the top row, back along the middle row, then along the bottom row.

Constraints

1 ≤ m, n ≤ 200
-2³¹ ≤ matrix[r][c] ≤ 2³¹ - 1

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern