Last Updated: 27 Nov, 2020
Find Longest Sequence
Moderate
Asked in company
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
Approaches
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’.
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’, a pointer to 2-D array ‘DP’, 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. If this subproblem is already solved, then return DP[ i ][ j ].
3. 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 call function ‘findLongestFromACell’ with parameters as ‘i’, ‘j+1’, MAT, DP, ‘n’ and store the result plus 1 in DP[ i ][ j ].
2. If ‘j’ is greater than zero and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i ][ j - 1 ] ), then call function ‘findLongestFromACell’ with parameters as ‘i’, ‘j-1’, MAT, DP, ‘n’ and store the result plus 1 in DP[ i ][ j ].
3. If ‘i’ is greater than zero and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i - 1 ][ j ] ), then call function ‘findLongestFromACell’ with parameters as ‘i-1’, ‘j’, MAT, DP, ‘n’ and store the result plus 1 in DP[ i ][ j ].
4. If ‘i’ is less than ‘N’ - 1 and ( MAT[ i ][ j ] + 1 ) equals ( MAT[ i + 1 ][ j ] ), then call function ‘findLongestFromACell’ with parameters as ‘i+1’, ‘j’, MAT, DP, ‘n’ and store the result plus 1 in DP[ i ][ j ].
4. If none of the adjacent fours are greater than the current cell, then store 1 in DP[ i ][ j ] and return it.
3. In function ‘findLongestOverAll’ with parameters as 2-D vector ‘MAT’ and integer ‘N’.
1. Initialize ‘RESULT’ as 1.
2. Create a lookup table and fill all entries as -1.
3. 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. Check if DP[ i ][ j ] equals -1, then, call function ‘findLongestFromACell’ with parameters as indices ‘i’ and ‘j’, 2-D vector ‘MAT’, 2-D array ‘DP’ and an integer ‘n’.
4. Update the ‘RESULT’ with maximum of ‘RESULT’ and DP[ i ][ j ].
This approach is also similar to the above approach. Here we will implement dynamic programming iteratively.
Algorithm :
1. We will implement a nested pair of vectors “vector<pair<int,pair<int,int>>>”
2. Then, we will iterate through 0 to ‘N-1’. (say, iterator ‘i’) , and we will again iterate through 0 to ‘N-1’ (say, iterator ‘j’) and will push MAT[ i ][ j ] and indices ‘i’ and ‘j‘ to the vector.
3. Sort the vector according to the increasing order of element MAT[ i ][ j ], by using the function ‘fun’.
4. Iterate through 0 to ‘N-1’. (say, iterator ‘i’) , and again iterate through 0 to ‘N-1’ (say, iterator ‘j’) and will assign ‘DP[ i ][ j ]’ as 1, where DP[ i ][ j ] denotes the maximum longest sequence possible if we will start from cell with row ‘i’ and column ‘j’.
5. Initialize variable ‘RESULT’ to INT_MIN.
6. Iterate through 0 to ‘N-1’. (say, iterator ‘k’).
1. Initialize ‘i’ as ‘VECT[k]’.second.first’ denoting the current row.
2. Initialize ‘j’ as ‘VECT[k]’.second.second’ denoting the current column.
3. Check if ‘i’ is greater than or equal to 1, and if MAT[ i ][ j ] - MAT[ i-1 ][ j ] equals 1, then, update ‘DP[ i ][ j ]’ with ‘DP[ i-1 ][ j ]’ plus 1.
4. Check if ‘j’ is greater than or equal to 1, and if MAT[ i ][ j ] - MAT[ i ][ j-1 ] equals 1, then, update ‘DP[ i ][ j ]’ with ‘DP[ i ][ j-1 ]’ plus 1.
5. Check if ‘i’ is less than ‘N’, and if MAT[ i ][ j ] - MAT[ i+1 ][ j ] equals 1, then, update ‘DP[ i ][ j ]’ with ‘DP[ i+1 ][ j ]’ plus 1.
6. Check if ‘j’ is less than ‘N’, and if MAT[ i ][ j ] - MAT[ i ][ j+1 ] equals 1, then, update ‘DP[ i ][ j ]’ with ‘DP[ i ][ j + 1] plus 1.
7. Update ‘RESULT’ with maximum of ‘RESULT’ and ‘DP[ i ][ j ]’.
7. Return ‘RESULT’.