Image Overlap LeetCode solution in Python

1
# Runtime: 593 ms (Top 76.00%) | Memory: 14.7 MB (Top 44.00%)
2
class Solution:
3
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
4
        n = len(img1)
5
        list1, list2 = [], []
6
        res = 0
7
        for r in range(n):
8
            for c in range(n):
9
                if img1[r][c]:
10
                    list1.append((r, c))
11
                if img2[r][c]:
12
                    list2.append((r, c))
13

14
        shiftDict = defaultdict(int)
15
        for x1, y1 in list1:
16
            for x2, y2 in list2:
17
                dx, dy = x2 - x1, y2 - y1
18
                shiftDict[(dx, dy)] += 1
19

20
        return max(shiftDict.values()) if shiftDict else 0