Increasing Path In Matrix

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
15 upvotes
Asked in companies
IntuitAppleOracle

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 2 
1 2
3 4
1 1
1
Sample Output 1 :
3
1
Explanation Of the Sample Input1 :
Test Case 1 :
The longest path is either 1,2,4 i.e (mat[0][0] ->mat[0][1] -> mat[1][2]), or it can be 1, 3, 4  i.e (mat[0][0] -> mat[1][0] -> mat[2][2]).  Length of the longest paths are 3.

Test Case 2 :
There is only one element in this matrix, so the length of the longest path will be 1.
Sample Input 2 :
2
2 2
1 1 
1 1
1 2
3 4
Sample Output 2 :
1
2
Explanation Of The Sample Input 2 :
Test Case 1 :
You cannot move from (0, 0) because both ‘mat[0][1]’ and ‘mat[1][0]’is not greater than ‘mat[0][0]’. Thus the length of the longest path will be 1. 

Test Case 2 :
The longest path is 3,4 i.e (mat[0][0] ->mat[0][1]).Length of the longest path is 2.
Hint

Try to find a recurrence relation

Approaches (3)
Recursion

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.
Time Complexity

O(2^(N+M)), where ‘N’, ‘M’ representing the number of rows and columns respectively.

 

The recursion depth can up to N+M in the worst case and in each step we make at most two recursive calls.

Space Complexity

O(N+M), where ‘N’, ‘M’ representing the number of rows and columns respectively.

 

The recursion depth will be of the order of (N+M).

Code Solution
(100% EXP penalty)
Increasing Path In Matrix
Full screen
Console