Last Updated: 11 Jan, 2021
Increasing Path In Matrix
Moderate
Asked in companies
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
Approaches
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.
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.
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.