Image Overlap — LeetCode 835 Python Solution

The 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.

Example

Input

img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]

Output

3

Explanation

We translate img1 to right by 1 unit and down by 1 unit.

Python solution

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        cnt = Counter()
        for i in range(n):
            for j in range(n):
                if img1[i][j]:
                    for h in range(n):
                        for k in range(n):
                            if img2[h][k]:
                                cnt[(i - h, j - k)] += 1
        return max(cnt.values()) if cnt else 0

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 835. Image Overlap is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems