Compute longest increasing path in matrix

Q: Compute longest increasing path in matrix

This question evaluates algorithmic problem-solving skills in graph traversal and dynamic programming on matrices, measuring understanding of state representation and performance trade-offs in grid-based searches within the Coding & Algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an m x n grid (matrix) of integers grid, where m >= 1 and n >= 1.

A path in the matrix is a sequence of cells where:

You may move from a cell only to one of its 4 neighbors: up, down, left, or right (no diagonals).
Each step must go to a cell with a strictly larger value than the current cell.

The length of a path is the number of cells in the path.

Task

Return the length of the longest strictly increasing path that can be found in the matrix.

You may start the path at any cell.

Example

For example, given:

grid = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]

One of the longest increasing paths is 1 → 2 → 6 → 9, so the answer is 4.

Constraints

1 <= m, n <= 200
-10^9 <= grid[i][j] <= 10^9

Your solution should be efficient enough to handle the largest inputs within typical interview time limits.

Compute longest increasing path in matrix

Overview

Comments (0)