Longest Increasing Path in a 2D Matrix Problem Statement

Given a matrix of non-negative integers of size 'N x M', where 'N' and 'M' denote the number of rows and columns respectively, find the length of the longest increasing path. You can move in any of the four directions: left, right, up, or down from each cell. Diagonal movement or moving outside the boundary of the matrix is not allowed.

Example:

Input:

3 2
2 2
5 6
6 9
5 11

Output:

3

Explanation:

In the given matrix, sequences like 3 → 5 → 6 and 3 → 5 → 9 form increasing paths of length 3 each.

Constraints:

1

Question

Longest Increasing Path in a 2D Matrix Problem Statement

Given a matrix of non-negative integers of size 'N x M', where 'N' and 'M' denote the number of rows and columns respectively, find the length of the longest increasing path. You can move in any of the four directions: left, right, up, or down from each cell. Diagonal movement or moving outside the boundary of the matrix is not allowed.

Example:

Input:

Output:

Explanation:

In the given matrix, sequences like 3 → 5 → 6 and 3 → 5 → 9 form increasing paths of length 3 each.

Constraints:

1 <= T <= 100
1 <= N <= 50
1 <= M <= 50
0 <= MATRIX[i] <= 10⁵

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Accepted Answer

The task is to find the length of the longest increasing path in a 2D matrix, where you can move in four directions: left, right, up, or down from each cell.

Traverse the matrix and for each cell, find the longest increasing path starting from that cell
Use dynamic programming to store the length of the longest increasing path for each cell
Recursively explore all four directions from each cell, checking if the next cell is greater than the current cell
Keep track of the maximum length of increasing path encountered