Grid Overlap

Easy
0/40
Average time to solve is 20m
15 upvotes
Asked in companies
AdobeIntuit

Problem statement

You are given two binary grids ‘MAT1’ and ‘MAT2’ of size N x N each. Both grids either have 0 or 1 written in each cell.

You can perform four types of operations to MAT1-

• Right Shift
• Left Shift
• Up Shift
• Down Shift

For eg:

Let the grid MAT1 be-


 After one right shift, it will look like-


After one left shift, it will look like-


After one up shift, it will look like-


After one down shift, it will look like-

You can perform any of the above operations in any order, any number of times(possibly zero) to MAT1.

Overlap of two grids is defined as the number of cells which have 1 written in it, in both the grids. Your task is to find the maximum possible overlap between ‘MAT1’ and ‘MAT2’ after applying some operations to ‘MAT1’.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains one integer ‘N’ denoting the number of rows and columns in the grid  ‘MAT1’ and ‘MAT2’.

The next ‘N’ lines of each test case contain ‘N’ space-separated integers each representing the rows of ‘MAT1’

The next ‘N’ lines of each test case contain ‘N’ space-separated integers each representing the rows of ‘MAT2’.
Output Format : 
For each test case, print the maximum possible overlap.

The output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 30
0 <= MAT1[i][j] <= 1
0 <= MAT2[i][j] <= 1

Time Limit: 1 sec.
Sample Input 1 :
2
3 
1 1 0
0 0 0
0 0 0
0 1 1
0 0 0
0 0 0
2
1 1
1 1
1 1
1 1
Sample Output 1:
2
4

Explanation for Sample 1:

The optimal answer for the first test case:

After applying one right shift to MAT1, we get it as-
  0 1 1
  0 0 0
  0 0 0
The overlap of MAT1 with MAT2 will be 2.


The optimal answer for the second test case:

We do not apply any shift to MAT1.
The overlap of MAT1 with MAT2 will be 4.
Sample Input 2 :
1
3  
1 1 0
0 1 0
0 1 0
0 0 0
0 1 1
0 0 1
Sample Output 2:
3
Hint

Check every cell of the grid.

Approaches (2)
Linear Transformations

For any cell A of MAT1 which has one and cell B of MAT2 which has one we can define linear transformation L as - (difference of X - coordinates of A and B, difference of Y - coordinates of A and B).  The cells which come under the same overlapping zone will have the same value of L.

 

The algorithm will be-

  • We will store all the cells which have ones in ‘MAT1’ in an array/list first.
  • We will store all the cells which have ones in ‘MAT2’ in an array/list second.
  • We will also declare a hashMap ‘frequency’, which stores the count of the linear transformation.
  • For each element in the first, we will find the value of L for each element of the second using two nested loops. Let this value be P.
    • We will increment ‘frequency[P]’ by 1.
  • The maximum count of an element in the hashmap ‘frequency’ will be our answer.
Time Complexity

O(N ^ 4), where N is the number of rows and columns of the grid.

 

In the worst-case, both MAT1 and MAT2 will be filled by ones and the size of array/list first and second will be at most O(N ^ 2). For each element of the first, we are iterating over each element of the second. Hence overall time complexity will be O(N ^ 4).  

Space Complexity

O(N ^ 2), where N is the number of rows and columns of the grid.

 

In the worst case, the size of both the first and the second can be O(N ^ 2).

Code Solution
(100% EXP penalty)
Grid Overlap
Full screen
Console