Compute longest increasing path in matrix

Q: Compute longest increasing path in matrix

This is a Coding & Algorithms interview question from Snapchat for Software Engineer roles. View the full question and solution on PracHub.

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

Comments (0)