Find Longest Sequence

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
27 upvotes
Asked in company
Amazon

Problem statement

You are given a ‘N’ * ‘N’ matrix where all numbers are distinct from (1 to N * N). You are required to find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.

Only four possible movements are allowed i.e, Up, Down, Left , and Right.

For example : 
Input:  Mat [ ][ ] = { { 9 , 1 , 3 }
                       { 7 , 4 , 2 }
                       { 6 , 5 , 8 } }
Output: 4
Explanation: The longest path is of length ‘4’ { 4 - 5 - 6 - 7 }
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains a single integer 'N' denoting the size of the matrix as N*N.
‘N’ lines follow. Each of the next ‘N’ lines contains ‘N’ space separated integers separated by space.
Output Format: 
For each test case, return an integer denoting the maximum length path.
Output for each test case should be printed in a separate line.
Note 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 100   
1 <= N <= 10^3

Time Limit : 1 sec
Sample Input 1:
2
3
1 2 9 
5 3 8
4 6 7 
4
1 15 13 14 
2 8 9 10 
3 11 16 12 
4 5 6 7
Sample Output 1:
4
7
Explanation For Sample Output 1 :
In test case 1:
For ‘N’ = 3,
1 2 9 
5 3 8
4 6 7
The longest path is of length ‘4’ { 6 -> 7 -> 8 -> 9 }

In test case 2:
For ‘N’ = 4,

1 15 13 14 
2 8  9  10 
3 11 16 12 
4 5  6 7

The longest path is of length ‘7’ { 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 }
Sample Input 2:
2
2
1 2
3 4
3
1 5 6
9 4 7
2 3 8
Sample Output 2:
2
7
Hint

Can we use a recursive function to calculate the longest path?

Approaches (3)
Recursion

1.  We will implement two functions namely, ‘findLongestFromACell’ to find the longest path starting from cell ( ‘i’, ‘j’ ) and function ‘findLongestOverAll’ to find the overall longest path satisfying the constraints.

2.  In function ‘findLongestFromACell’ with parameters as indices ‘i’ and ‘j’, 2-D vector ‘MAT’ and an integer ‘n’.

   1.  Checking the base condition, if either ‘i’ or ‘j’ is less than zero or is greater than or equal to ‘N’, simply return.

   2.  Since all numbers are unique and in range from 1 to ‘N’ * ‘N’, there is at most one possible direction from any cell.

       1.  If ‘j’ is less than ‘N’ - 1 and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i ][ j + 1 ] ), then return 1 + call the function ‘findLongestFromACell’ with parameters as ‘i’, ‘j+1’, ‘MAT’, ‘n’.

       2.  If ‘j’ is greater than zero and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i ][ j - 1 ] ), then return 1 + call the function ‘findLongestFromACell’ with parameters as ‘i’, ‘j-1’, ‘MAT’, ‘n’.

       3.  If ‘i’ is greater than zero and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i - 1 ][ j ] ), then return 1 + call the function ‘findLongestFromACell’ with parameters as ‘i-1’, ‘j’, ‘MAT’, ‘n’.

       4.  If ‘i’ is less than ‘N’ - 1 and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i + 1 ][ j ] ), then return 1 +  call the function ‘findLongestFromACell’ with parameters as ‘i+1’, ‘j’, ‘MAT’, ‘n’.

       5.  Return 1.

   3.  In function ‘findLongestOverAll’ with parameters as 2-D vector ‘MAT’ and integer ‘N’.

       1.  Initialize ‘RESULT’ as 1.

       2.  Compute the longest path beginning from all cells.

           1.  Iterate from 0 to ‘N-1’ (say, iterator = ‘i’).

           2.  Iterate from 0 to ‘N-1’ (say, iterator = ‘j’).

           3.  Call function ‘findLongestFromACell’ with parameters as indices ‘i’ and ‘j’, 2-D vector ‘MAT’ and an integer ‘N’.

           4.  Update the ‘RESULT’ with maximum of ‘RESULT’ and the value returned by calling the function ‘findLongestFromACell’.

Time Complexity

O(2^N), where ‘N’ is the number of rows and number of columns of the 2-D Matrix.

 

As we have two choices either to include the cell or to exclude the cell.

Space Complexity

O(N^2), where ‘N’ is the number of rows and number of columns of the 2-D Matrix.

 

As there are N^2 elements hence, the height of the stack can be N^2 in the worst case.

Code Solution
(100% EXP penalty)
Find Longest Sequence
Full screen
Console