Bare given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.) We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images. (Note also that a translation does not include any kind of rotation.) What is the largest possible overlap? Notes:
1 <= A.length = A.length = B.length = B.length <= 30
0 <= A[i][j], B[i][j] <= 1
This post will cover three approaches, especially the third one involves some tricks to make the programme shorter and fancier.
Assuming the dimension of the matrix is
n*n, we can exhaust all possible shifts (row\pmx,col\pmy), x \in (0...n) and y \in (0...n). Notably, For each shifting, we need to consider cases where moving A referring to B and moving B referring to A.
Time complexity would be O(n^4) as there are O(n^2) combinations of shifts and for each shift we take O(n^2) to find the overlaps.
class Solution: def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int: n = len(A) def count(x_offset,y_offset,M,R): cnt = 0 # using enuermate() to generate two indices for r_row,m_row in enumerate(range(y_offset,n)): for r_col,m_col in enumerate(range(x_offset,n)): cnt += M[m_row][m_col] == R[r_row][r_col] == 1 return cnt ret = 0 for y_offset in range(n): for x_offset in range(n): ret = max(ret,count(x_offset,y_offset,A,B),count(x_offset,y_offset,B,A)) return ret
Optimized 1 – Hashmap
In the previous approach, we spent much time on scanning the entire matrix, which might waste too much time when processing sparse matrices. To improve it we can focus on
1-s in both matrices. When we try to find overlaps after shifting, we can instead look for cells from
B such that they are all
1-s and they share the same shifts.
We can implement this approach by finding all
1-s in both
B and use the hashmap – with shifting vectors as the key – to count the number of cells that share the same shifts.
class Solution: def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int: n = len(A) def count_1(M): ret =  for r in range(n): for c in range(n): if M[r][c] == 1: ret.append((r,c)) return ret dic = collections.defaultdict(int) max_overlap = 0 A_1 = count_1(A) B_1 = count_1(B) for r_A,c_A in A_1: for r_B,c_B in B_1: vec = (r_A-r_B,c_A-c_B) dic[vec] += 1 max_overlap = max(max_overlap,dic[vec]) return max_overlap
Optimized 2 – 2-dimension key to 1-dimension key
Another great approach from @lee215, the logic is almost the same, but some tricks are applied:
- Instead of iterating as
for row in range(n) for col in range(n), we can iterate
range(0,n*n)so the row is
- Instead of using
(row,col)to record the positions, we can convert it into an integer
row*n+colwould work (n<=30 as shown in the question) but noticing that we are moving two directions – moving A referring to B and moving B referring to A, therefore
colcould be negative and there are cases when row*n+col cannot differentiate each case. For example, shifting 615 could be
21*30-15. Therefore we need at least
row*2n+col. For simplicity, we can use
class Solution: def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int: n = len(A) A_1 = [i//n*100+i%n for i in range(n**2) if A[i//n][i%n]==1] B_1 = [i//n*100+i%n for i in range(n**2) if B[i//n][i%n]==1] c = collections.Counter(a-b for a in A_1 for b in B_1) return max(c.values() or )