Find Longest Sequence

Posted: 27 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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 }
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
Approach 1

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’.

Try Problem