DIY: Longest Increasing Path in a Matrix

Solve the interview question "Longest Increasing Path in a Matrix" in this lesson.

Problem statement

You are given an m x n matrix. You have to return the length of the longest increasing path in this matrix.

From each cell, you can move in any one of four directions: left, right, up, or down. You may not move diagonally or move outside the matrix’s boundaries.

Input

The input will be an m x n matrix of integers. The following is an example input:

matrix = [
[3,4,5],
[3,2,6],
[2,2,1]
]

Output

The output will be an integer value representing the longest path. The following is an example output for the above input:

4

The longest increasing path with required constraints, comes out to be [3, 4, 5, 6].

Coding exercise

Implement the longest_increasing_path(matrix) function, where matrix is the m x n matrix of integers. The function will return a single integer value representing the number of cells in the longest path.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.