Last Updated: 10 Feb, 2021
Ninja and his sword
Moderate
Asked in company
Ninja has been given two integer matrices ‘MAT1’ and ‘MAT2’ of sizes 'N1 x M1' and 'N2 x M2', respectively. He is also given a magic sword. Using this sword, he can cut a sub-square of any size from the given matrices if it is present in both the matrices. Formally, he can cut that sub-square from the first matrix which is also present in the other matrix with the same values inside both sub-squares.
However, Ninja can use this magic sword only once. So, he decides to cut that common sub-square which has the largest size.
For example:
For the matrices 'MAT1' and 'MAT2' as shown in the image below, the largest sub-square which is common in both of the matrices is of size 2.
Can you help Ninja achieve this task?
Note:
If there is no such sub-square present then return 0.
Input Format:
The first line of input contains an integer 'T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains two single space-separated integers ‘N1’ and ‘M1’ representing the size of the matrix ‘MAT1’.
The next ‘N1’ lines of each test case contain ‘M1’ single space-separated integers denoting the values of ‘MAT1’.
The next line of each test case contains two single space-separated integers ‘N2’ and ‘M2’ representing the size of the matrix ‘MAT2’.
The next ‘N2’ lines of each test case contain ‘M2’ single space-separated integers denoting the values of ‘MAT2’.
Output Format :
For each test case, print a single line containing a single integer denoting the size of the largest possible sub-square which is also present in another matrix.
The output of each test case will be printed in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 100
1 <= ‘N1, ‘M1’, ‘N1’, ‘M2’ <= 50
1 <= ‘MAT1[ i ][ j ]’, ‘MAT2[ i ][ j ]’ <=10000
Time limit: 1 sec.
Approaches
Hashing will allow us to represent the whole sub-square as a single number. Then for comparing the sub-square present in both the matrices, we just compare the corresponding numbers. We make hash matrices ‘HashMatA’ and ‘HashMatB’ corresponding to the input matrices ‘MAT1’ and ‘MAT2’. We use the idea of the Rabin-karp pattern matching algorithm and modify it for calculating the hash value which is a single number representing 2-D matrices.
Here is the algorithm :
- We declare two matrices ‘HashMatA’ and ‘HashMatB’ in which we store the hash values of the ‘MAT1’ and ‘MAT2’ respectively by applying the Rabin Karp 2D algorithm.
- We select a size of the sub-square by applying the binary search algorithm as discussed in the previous approach.
- We store all the hash values for the given size of the square into a set ‘hashValueOfMat1’ from matrix ‘MAT1’.
- Then we traverse through the ‘MAT2’ :
- Calculate a hash value for every subsquare of a given size and check if this hash value is present in the set ‘hashValueOfMat1’.
- If the current hash value is present in the set then return true.
- If we find a sub-square with the given size in both the matrices then we check for some higher value.
- Else, we check for some lower value.
- Finally, we return the answer.