Ninja and his sword

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

Problem statement

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.

matrix

Can you help Ninja achieve this task?

Note:

If there is no such sub-square present then return 0.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3 3
0 1 1
1 1 1
0 1 1
3 3
1 0 1
1 1 1
0 1 1
2 2
1 2
3 4
2 2
5 6
7 8
Sample Output 1:
2
0

Explanation for Sample Output 1:

For sample test case 1: 
The largest sub-square which is common in both of the matrices is of size 2 as shown below.

MAT1

For sample test case 2:
There is no such sub-square that is common in both the matrices, so our answer is 0.

MAT2

Sample Input 2:
2
2 2
1 2
1 2
2 2
1 2
1 2
2 3
1 2 3
2 1 3
3 2
2 3
1 3
1 2
Sample Output 2:
2
2

Explanation for Sample Output 2:

For sample test case 1: 
In this sample test case, both matrices are equal. So largest sub-square which is common in both of the matrices is of size 2.

MAT3

For sample test case 2:
The largest sub-square which is common in both of the matrices is of size 2 as shown below.

MAT4

Hint

Can we use Rabin Karp algorithm?

Approaches (1)
Rabin Karp 2D algorithm

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 :

  1. 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.
  2. We select a size of the sub-square by applying the binary search algorithm as discussed in the previous approach.
  3. We store all the hash values for the given size of the square into a set ‘hashValueOfMat1’ from matrix ‘MAT1’.
  4. 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.
  5. If we find a sub-square with the given size in both the matrices then we check for some higher value.
  6. Else, we check for some lower value.
  7. Finally, we return the answer.
Time Complexity

O(log(N1) * (N2 * M2)) where ‘N1’ denotes the number of rows of the matrix ‘MAT1’ and  ‘N2’  and ‘M2’ denotes the number of rows and columns of the matrix ‘MAT2’.

 

To find the maximum size of the sub-square we are applying binary search. We traverse in the ‘MAT1’ and push all its values into ‘hashValueOfMat1’. Then we traverse the other matrix ‘MAT2’ and find if the hash value of the given size of the sub-square is present in ‘hashValueOfMat1’ or not. Hence, the overall time complexity is O(log(N1) * (N2 * M2)).

Space Complexity

O(N1 * M1) + O(N2 * M2)  Where ‘N1’ and ‘M1’ denote the number of rows and columns of the matrix ‘MAT1’ and  ‘N2’  and ‘M2’ denotes the number of rows and columns of the matrix ‘MAT2’.

 

 

We are using extra matrices of sizes ‘N1 * M1’ and ‘N2 * M2’  to store the hash values of ‘MAT1’ and ‘MAT2’ respectively. We also use the set ‘hashValueOfMat1’ to store values of ‘MAT1’ i.e O(N1 * M1). In the worst-case i.e when the size of sub-square is 1, then we are pushing hash value for all elements of ‘MAT1’. Hence the overall space complexity is O(N1 * M1) + O(N2 * M2).

Code Solution
(100% EXP penalty)
Ninja and his sword
Full screen
Console