Increasing Path In Matrix

PROBLEM STATEMENT

You are given a 2-D matrix ‘mat’, consisting of ’N’ rows and ‘M’ columns. The element at the i-th row and j-th column is ‘mat[i][j]’.

From mat[i][j], you can move to mat[i+1][j] if mat[i+1][j] > mat[i][j], or to mat[i][j+1] if mat[i][j+1] > mat[i][j].

Your task is to find and output the longest path length if you start from (0,0) i.e from mat[0][0] and end at any possible cell (i, j) i.e at mat[i][j].

Note :

Consider 0 based indexing.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases are as follows -: 

The first line contains two space-separated positive integers ‘N’, ‘M’ representing the number of rows and columns respectively.

Each of the next ‘N’ lines contains ‘M’ space-separated integers that give the description of the matrix ‘mat’.

Output Format :

For each test case, print the length of the longest path in the matrix.

Print the output of each test case in a separate line.

Note :

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

Constraints :

1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
-10^9 <= mat[i][j] <= 10^9

Time Limit: 1 sec

Approach 1

Algorithm

This is a recursive approach.
Make a recursive function ‘helper(row, col)’ and call this function with (0, 0). In each recursive step do the following-:
- Initialize an integer variable ‘temp’: = 0.
- If cell (row+1, c) exist and mat[row+1][col] > mat[row][col], then recursively call ‘helper(row+1, col)’ and update ‘temp’ with maximum of ‘temp’ and value return by ‘helper(row+1, col)’.
- If cell (row, col+1) exist and mat[row][col+1] > mat[row][col], then recursively call ‘helper(row, col+1)’ and update ‘temp’ with maximum of ‘temp’ and value return by ‘helper(row, col+1)’.
- Return ‘temp’ + 1.
The value returned by helper(0, 0) will be the length of the longest path start from (0, 0), we need to return this value.

Try Problem

Approach 2

In the recursive approach, we can observe that we are doing a lot of repeated work here. To avoid doing repeated work we can memoize the already computed result in a table.

Algorithm

This is a recursive approach.
Make an integer matrix ‘memo’ of dimension n*m to memoize already computed results. Fill this matrix by -1.
Make a recursive function ‘helper(row, col)’ and call this function with (0, 0). In each recursive step do the.
- If ‘memo[row][col]’ != -1, return ‘memo[row][col]’.
- Initialize an integer variable ‘temp’: = 0.
- If cell (row+1, c) exist and mat[row+1][col] > mat[row][col], then recursively call ‘helper(row+1, col)’ and update ‘temp’ with maximum of ‘temp’ and value return by ‘helper(row+1, col)’.
- If cell (row, col+1) exist and mat[row][col+1] > mat[row][col], then recursively call ‘helper(row, col+1)’ and update ‘temp’ with maximum of ‘temp’ and value return by ‘helper(row, col+1)’.
- Assign ‘memo[row][col]’ = ‘temp+1’
- Return ‘memo[row][col]’.
The value returned by helper(0, 0) will be the length of the longest path start from (0, 0), we need to return this value.

Try Problem

Approach 3

The idea is to use dynamic programming. Maintain the 2D matrix ‘dp’ of size n*m, where dp[i][j] stores the length of the longest path ending at the ith row and jth column i.e at mat[i][j].

Algorithm

Create a 2D integer matrix ‘dp’ of size n*m, where dp[i][j] stores the length of the longest path ending at ‘mat[i][j]’. Fill the entire matrix ‘dp[][]’ with INT_MIN initially.
Assign dp[0][0]:= 1
Run a loop where ‘i’ ranges from 1 to ‘m-1’ and for each ‘i’ if ‘mat[0][i]’ > mat[0][i-1], then assign dp[0][i] := dp[0][i-1] + 1, otherwise break the loop.
Run a loop where ‘i’ ranges from 1 to ‘n-1’ and for each ‘i’ if ‘mat[i][0]’ > mat[i-1][0]’, then assign dp[i][0] := dp[i-1][0] + 1, otherwise break the loop
Run two nested loops, In outer loop ‘i’ ranges from 1 to n-1, and inner loop ‘j’ ranges from 1 to m-1, and for each (i, j) do the following.
- If mat[i][j] > mat[i][j-1], then assign dp[i][j] = max(dp[i][j], dp[i][j-1] + 1).
- If mat[i][j] > mat[i-1][j], then assign dp[i][j] = max(dp[i][j], dp[i-1][j] + 1).
The largest value of the matrix ‘dp[][]’ will be the length of the longest path starting from (0, 0), we need to return this value.

Try Problem