September 13Medium

Image overlap

Array
Matrix

Problem

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.

Solution

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        m, n = len(img1), len(img1[0])

        ans = 0
        for dx in range(-m+1, m):
            for dy in range(-n+1, n):
                local_ans = 0
                x_start, x_end = (0, m - dx) if dx >= 0 else (abs(dx), m)
                y_start, y_end = (0, n - dy) if dy >= 0 else (abs(dy), n)

                for x in range(x_start, x_end):
                    for y in range(y_start, y_end):
                        if img1[x][y] == img2[x + dx][y + dy] == 1:
                            local_ans += 1
                ans = max(ans, local_ans)

        return ans