Problem statement

https://binarysearch.com/problems/Image-Intersection/

Solution

Equal to Leetcode 0835. Image Overlap.

Complexity

It is O(m^2n^2) for time and O(mn) for space.

Code

class Solution:
    def solve(self, A, B):
        if not A or not B: return 0
        d = Counter()
        a, b, m, n, ans = [], [], len(A), len(A[0]), 0
        for i, j in product(range(m), range(n)):
            if A[i][j]: a += [(i, j)]
            if B[i][j]: b += [(i, j)]
        for t1, t2 in product(a, b):
            t3 = (t2[0] - t1[0], t2[1] - t1[1])
            d[t3] += 1
            ans = max(ans, d[t3])
        return ans