You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.Return the largest possible overlap.
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]Output: 3Explanation: We translate img1 to right by 1 unit and down by 1 unit.
The number of positions that have a 1 in both images is 3 (shown in red).
from collections import Counterclass Solution: # Time: O(n^4) where n is the image size (pairs of 1 bits across both images) # Space: O(n^2) for the shift counter def largest_overlap(self, img1: list[list[int]], img2: list[list[int]]) -> int: ones1 = [(i, j) for i, row in enumerate(img1) for j, val in enumerate(row) if val] ones2 = [(i, j) for i, row in enumerate(img2) for j, val in enumerate(row) if val] shifts: Counter[tuple[int, int]] = Counter() best = 0 for i1, j1 in ones1: for i2, j2 in ones2: shift = (i2 - i1, j2 - j1) shifts[shift] += 1 best = max(best, shifts[shift]) return best
The number of positions that have a 1 in both images is 3 (shown in red).
