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 longestIncreasingPath(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.