You are given two images img1 and img2 both of size n x n, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)
We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image.  After, the overlap of this translation is the number of positions that have a 1 in both images.
(Note also that a translation does not include any kind of rotation.)
What is the largest possible overlap?
 
Example 1:

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 slide 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)


Example 2:
Input: img1 = [[1]], img2 = [[1]]
Output: 1

Example 3:
Input: img1 = [[0]], img2 = [[0]]
Output: 0

 
Constraints:

n == img1.length
n == img1[i].length
n == img2.length 
n == img2[i].length
1 <= n <= 30
img1[i][j] is 0 or 1.
img2[i][j] is 0 or 1.

Difficulty: interview

Starter code:

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def largestOverlap(self, A, B) -> int:
        leng = len(A[0])

        # convert A, B to binary
        a = 0
        b = 0
        for i in range(0, leng * leng):
            row = int(i % leng)
            col = int(i / leng)
            a = (a << 1) + A[col][row]
            b = (b << 1) + B[col][row]

        maxsum = 0
        for i in range(-leng + 1, leng):
            if i < 0:
                mask = ('0' * abs(i) + '1' * (leng - abs(i))) * leng
                bp = (b & int(mask, 2)) << abs(i)
            elif i > 0:
                mask = ('1' * (leng - abs(i)) + '0' * abs(i)) * leng
                bp = (b & int(mask, 2)) >> abs(i)
            else:
                bp = b

            for j in range(-leng + 1, leng):
                if j < 0:
                    bpp = bp >> (leng * abs(j))
                elif j > 0:
                    bpp = (bp << (leng * abs(j))) & ((2 ** (leng * leng)) - 1)
                else:
                    bpp = bp
                maxsum = max(maxsum, bin(a & bpp).count('1'))

        return maxsum

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        ct = Counter()
        for i, row in enumerate(A):
            for j, col in enumerate(row):
                if col:
                    for i2, row2 in enumerate(B):
                        for j2, col2 in enumerate(row2):
                            if col2:
                                ct[i - i2, j - j2] += 1
        return max(ct.values() or [0])

class Solution(object):
    def largestOverlap(self, A, B):
        count = [0] * (2*len(A)-1)**2
        for i, row in enumerate(A):
            for j, v in enumerate(row):
                if not v:
                    continue
                for i2, row2 in enumerate(B):
                    for j2, v2 in enumerate(row2):
                        if not v2:
                            continue
                        count[(len(A)-1+i-i2)*(2*len(A)-1) +
                              len(A)-1+j-j2] += 1
        return max(count)

import collections
class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        count = collections.Counter()
        for i, rowa in enumerate(A):
            for j in range(len(rowa)):
                if rowa[j]:
                    for m, rowb in enumerate(B):
                        for n in range(len(rowb)):
                            if rowb[n]:
                                count[i-m, j-n] += 1
        return max(list(count.values()) or [0])
        
        
        
        
        
        


class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        ct = Counter()
        for i, row in enumerate(A):
            for j, col in enumerate(row):
                if col:
                    for i2, row2 in enumerate(B):
                        for j2, col2 in enumerate(row2):
                            if col2:
                                 ct[i - i2, j - j2] += 1
        # print(ct)
        return max(ct.values() or [0])

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        dic = {}
        for i in range(len(A)):
            for j in range(len(A[i])):
                pos = A[i][j]
                if pos != 1: continue
                for x in range(len(B)):
                    for y in range(len(B[x])):
                        pos = B[x][y]
                        if pos != 1: continue
                        xdiff, ydiff = y - j, x - i
                        if (xdiff,  ydiff) not in dic:
                            dic[(xdiff,  ydiff)] = 1
                        else: dic[(xdiff,  ydiff)] += 1
        if len(dic) == 0: return 0
        return max(dic.values())

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        
        
        # get non-zeros
        def nonzero_cells(matrix):
            ones = []
            for r in range(len(matrix)):
                for c in range(len(matrix[r])):
                    if matrix[r][c] == 1:
                        ones.append((r, c))
            return ones
        
        a = nonzero_cells(A)
        b = nonzero_cells(B)
        overlap_vectors = defaultdict(int)
        
        max_overlap = 0
        for x_a, y_a in a:
            for x_b, y_b in b:
                overlap_vector = ((x_b - x_a, y_b - y_a))
                overlap_vectors[overlap_vector] += 1
                max_overlap = max(max_overlap, overlap_vectors[overlap_vector])
        
        return max_overlap

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        counts, best = {}, 0
        size = len(A[0])
        for x1 in range(size):
            for y1 in range(size):
                if A[y1][x1] == 1:
                    for x2 in range(size):
                        for y2 in range(size):
                            if B[y2][x2] == 1:
                                diff = (x2-x1, y2-y1)
                                counts[diff] = counts.get(diff, 0) + 1
                                best = counts[diff] if counts[diff] > best else best
        return best


#
# @lc app=leetcode id=835 lang=python3
#
# [835] Image Overlap
#

# @lc code=start
from functools import lru_cache
from copy import deepcopy

@lru_cache(None)
def countBits(n):
    return 0 if n == 0 else (n & 1) + countBits(n >> 1)

class Solution:
    def stateCompress(self, img):
        n, m = len(img), len(img[0])
        rows = [0 for _ in range(n)]
        for i, row in enumerate(img):
            for e in row:
                rows[i] = (rows[i] << 1) + e
        return n, m, rows
    
    
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n, m, rA = self.stateCompress(A)
        _, _, rB = self.stateCompress(B)

        def shift(arr1, arr2, l):
            return sum(countBits(e1 & e2) for e1, e2 in zip(arr1[:l], arr2[n-l:n]))

        maxOverLap = 0
        tA = deepcopy(rA)
        tB = deepcopy(rB)
        
        for dc in range(m):
            for dr in range(1, n + 1):
                maxOverLap = max(maxOverLap, shift(tA, rB, dr))
                maxOverLap = max(maxOverLap, shift(tB, rA, dr))
            tA = [ e >> 1 for e in tA]
            tB = [ e >> 1 for e in tB] 
        return maxOverLap
                
                
# @lc code=end



#
# @lc app=leetcode id=835 lang=python3
#
# [835] Image Overlap
#

# @lc code=start
from functools import lru_cache
from copy import deepcopy

@lru_cache(None)
def countBits(n):
    if n == 0:
        return 0
    return (n & 1) + countBits(n >> 1)

class Solution:
    def stateCompress(self, img):
        n, m = len(img), len(img[0])
        rows = [0 for _ in range(n)]
        for i, row in enumerate(img):
            for e in row:
                rows[i] = (rows[i] << 1) + e
        return n, m, rows
    
    
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n, m, rA = self.stateCompress(A)
        _, _, rB = self.stateCompress(B)

        def shift(arr1, arr2, l):
            return sum(countBits(e1 & e2) for e1, e2 in zip(arr1[:l], arr2[n-l:n]))

        maxOverLap = 0
        tA = deepcopy(rA)
        tB = deepcopy(rB)
        
        for dc in range(m):
            for dr in range(1, n + 1):
                maxOverLap = max(maxOverLap, shift(tA, rB, dr))
                maxOverLap = max(maxOverLap, shift(tB, rA, dr))
            tA = [ e >> 1 for e in tA]
            tB = [ e >> 1 for e in tB] 
        return maxOverLap
                
                
# @lc code=end



class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        
        s1 = set()
        s2 = set()
        
        for j,row in enumerate(img1):
            for i,v in enumerate(row):
                if v == 1:
                    s1.add((j,i))
        for j,row in enumerate(img2):
            for i,v in enumerate(row):
                if v == 1:
                    s2.add((j,i))
        
        d = {}
        
        for x in s1:
            for y in s2:
                v0 = x[0]-y[0]
                v1 = x[1]-y[1]
                
                vv = (v0,v1)
                if vv in d:
                    d[vv] += 1
                else:
                    d[vv] = 1
        
        dl = sorted(list(d.items()), key=lambda x:x[1])
        
        if not len(dl):
            return 0
        
        return dl[-1][1]

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        # Opcion 1
        # Dejo A fija 
        # Genero todas las variaciones de B
        # Cruzo una por una con A con AND y cuento los 1 por cada matriz
        # Me quedo con el maximo
        # Optimizo: Puedo cortar cuando encuentro un overlap que sea igual a la cantidad de 1 de mi matriz A
        
        # Opcion 2 
        # Dejo A fija
        # Itero por B y armo una lista de elementos con sus indices
        # Luego por cada uno, lo superpongo con cada indice del otro 
        def get_movement(a, b):
            x = a[0] - b[0]
            y = a[1] - b[1]
            return (x, y)
        # def check_movement(move):
        #     counter = 0
        #     for val in B_elements:
        #         x = (val[0] + move[0])
        #         y = (val[1] + move[1])
        #         if (x,y) in A_elements:
        #             counter += 1
        #     return counter
        
        A_elements = []
        B_elements = []
        dimension = None
        for i, row in enumerate(A):
            for j, val in enumerate(row):
                if val == 1:
                    A_elements.append((i,j))
                if B[i][j] == 1:
                    B_elements.append((i,j))
        dimension = i + 1
        maximo = 0
        A_len = len(A_elements)
        B_len = len(B_elements)
        maximo_posible = min(A_len, B_len)
        # moved = set()
        moved = {}
        for elem_A in A_elements:
            for elem_B in B_elements:
                move = get_movement(elem_A, elem_B)
                if move not in list(moved.keys()):
                    moved[move] = 1
                else:
                    moved[move] += 1
                
                if moved[move] > maximo:
                    maximo = moved[move]
                    if maximo >= maximo_posible:
                        break
                # if not move in moved:
                #     moved.add(move)
                #     res = check_movement(move)
                #     if res > maximo:
                #         maximo = res
                #         if maximo >= maximo_posible:
                #             break

        return maximo



class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        # Opcion 1
        # Dejo A fija 
        # Genero todas las variaciones de B
        # Cruzo una por una con A con AND y cuento los 1 por cada matriz
        # Me quedo con el maximo
        # Optimizo: Puedo cortar cuando encuentro un overlap que sea igual a la cantidad de 1 de mi matriz A
        
        # Opcion 2 
        # Dejo A fija
        # Itero por B y armo una lista de elementos con sus indices
        # Luego por cada uno, lo superpongo con cada indice del otro 
        def get_movement(a, b):
            x = a[0] - b[0]
            y = a[1] - b[1]
            return (x, y)
        def check_movement(move):
            counter = 0
            for val in B_elements:
                x = (val[0] + move[0])
                y = (val[1] + move[1])
                if (x,y) in A_elements:
                    counter += 1
            return counter
        
        A_elements = set()
        B_elements = []
        dimension = None
        for i, row in enumerate(A):
            for j, val in enumerate(row):
                if val == 1:
                    A_elements.add((i,j))
                if B[i][j] == 1:
                    B_elements.append((i,j))
        dimension = i + 1
        maximo = 0
        A_len = len(A_elements)
        B_len = len(B_elements)
        maximo_posible = min(A_len, B_len)
        # moved = set()
        moved = {}
        for elem_A in A_elements:
            for elem_B in B_elements:
                move = get_movement(elem_A, elem_B)
                if move not in list(moved.keys()):
                    moved[move] = 1
                else:
                    moved[move] += 1
                
                if moved[move] > maximo:
                    maximo = moved[move]
                    if maximo >= maximo_posible:
                        break
                # if not move in moved:
                #     moved.add(move)
                #     res = check_movement(move)
                #     if res > maximo:
                #         maximo = res
                #         if maximo >= maximo_posible:
                #             break
        print(moved)
        return maximo



class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        offset_map = {}
        max_overlap = 0
        for row in range (0, len(A)):
            offset_map[row] = {}
            offset_map[row * -1] = {}
            for col in range (0, len(A[row])):
                r_row = row
                r_col = col
                if not offset_map[r_row] or not r_col in offset_map[r_row] or not offset_map[r_row][r_col]:
                    overlap = self.shift_and_count(A, B, r_row, r_col)
                    overlap = max(overlap, self.shift_and_count(B, A, r_row, r_col))
                    max_overlap = max(overlap, max_overlap)
                    offset_map[r_row][r_col] = overlap
        return max_overlap
                        
    def shift_and_count(self, A: List[List[int]], B: List[List[int]], row_shift: int, col_shift: int) -> int:
        result = 0
        for row in range(len(A)):
            new_row = row - row_shift
            if new_row >= 0 and new_row < len(A):
                for col in range(len(A[row])):
                    new_col = col - col_shift
                    if ((new_col >= 0 and new_col < len(A[row]))):
                        if (A[new_row][new_col] == 1) and B[row][col] == 1:
                            result += 1
                            
        return result
    
    def overlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        overlap = 0
        if len(A) != len(B):
            raise ValueError
        for row in range(0, len(A)):
            for col in range(0, len(A[row])):
                if len(A[row]) != len(B[row]):
                    raise ValueError
                if A[row][col] == 1 and B[row][col] == 1:
                    overlap += 1
        return overlap
    
    


def mat_to_set(A):
    return {(i, j) for i, row in enumerate(A) for j, bit in enumerate(row) if bit}

class Solution:
    def largestOverlap(self, A, B) -> int:
        N = len(A)
        A, B = mat_to_set(A), mat_to_set(B)
        
        if len(A) > len(B):
            A, B = B, A
    
        max_overlap = 0
        for di in range(1 - N, N):
            for dj in range(1 - N, N):
                overlap = 0
                for i, j in A:
                    if (i + di, j + dj) in B:
                        overlap += 1
                max_overlap = max(max_overlap, overlap)

        return max_overlap

def mat_to_set(A):
    return {(i, j) for i, row in enumerate(A) for j, bit in enumerate(row) if bit}

def overlap(A, B, di, dj):
    count = 0
    for i, j in A:
        if (i + di, j + dj) in B:
            count += 1
    return count

class Solution:
    def largestOverlap(self, A, B) -> int:
        offsets = range(1 - len(A), len(A))
        A, B = mat_to_set(A), mat_to_set(B)
        
        if len(A) > len(B):
            A, B = B, A
    
        return max(overlap(A, B, di, dj) for di in offsets for dj in offsets)

def mat_to_set(A):
    return {(i, j) for i, row in enumerate(A) for j, bit in enumerate(row) if bit}

class Solution:
    def largestOverlap(self, A, B) -> int:
        offsets = range(1 - len(A), len(A))
        A, B = mat_to_set(A), mat_to_set(B)
        
        if len(A) > len(B):
            A, B = B, A
            
        def overlap(di, dj):
            count = 0
            for i, j in A:
                if (i + di, j + dj) in B:
                    count += 1
            return count
    
        return max(overlap(di, dj) for di in offsets for dj in offsets)

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        max_count = 0
        
        a_coords = self.coordinates(A)
        b_coords = self.coordinates(B)
        
        for v in range(-1 * (len(A) - 1), len(A)):
            for h in range(-1 * (len(A[0]) - 1), len(A[0])):
                overlap_count = 0
                for r, c in a_coords:                    
                    if (r + v, c + h) in b_coords:
                        overlap_count += 1
            
                max_count = max(max_count, overlap_count)
                
        return max_count
        
    def coordinates(self, image):
        coords = set()
        for r, row in enumerate(image):
            for c, value in enumerate(row):
                if value == 1:
                    coords.add((r, c))
        return coords

#
# @lc app=leetcode id=835 lang=python3
#
# [835] Image Overlap
#

# @lc code=start
from functools import lru_cache

@lru_cache
def countBits(n):
    if n == 0:
        return 0
    return (n & 1) + countBits(n >> 1)

class Solution:
    def stateCompress(self, img):
        n, m = len(img), len(img[0])
        rows = [0 for _ in range(n)]
        for i, row in enumerate(img):
            for j, e in enumerate(row):
                rows[i] = (rows[i] << 1) + e
        return n, m, rows
    
    
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n, m, rA = self.stateCompress(A)
        _, _, rB = self.stateCompress(B)

        @lru_cache
        def shift(xAs, xAe, xBs, xBe, dy):
            if dy > 0:
                ret = list(countBits((e1 << dy) & e2) for e1, e2 in zip(rA[xAs:xAe], rB[xBs:xBe]))
                return ret
            else:
                dy = -dy
                ret = list(countBits((e1 >> dy) & e2) for e1, e2 in zip(rA[xAs:xAe], rB[xBs:xBe]))
                return ret

        print((rA, rB))
        maxOverLap = 0
        for dr in range(n):
            for dc in range(m):
                maxOverLap = max(maxOverLap, sum(shift(dr, n, 0, n - dr, dc)))
                maxOverLap = max(maxOverLap, sum(shift(0, dr, n - dr, n, dc)))
                maxOverLap = max(maxOverLap, sum(shift(dr, n, 0, n - dr, -dc)))
                maxOverLap = max(maxOverLap, sum(shift(0, dr, n - dr, n, -dc)))
        return maxOverLap
                
                
# @lc code=end



class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        # define the iteration scheme
        size = len(A)
        shifts = [ii for ii in range(size)]

        # count overlap
        max_overlap = 0
        for x in shifts:
            for y in shifts:
                max_overlap = max(
                    self.shift_and_count(x_shift=x, y_shift=y, array_reference=A, array_to_be_shifted=B), max_overlap
                )
                max_overlap = max(
                    self.shift_and_count(x_shift=x, y_shift=y, array_reference=B, array_to_be_shifted=A), max_overlap
                )
        return max_overlap

    def shift_and_count(
            self, x_shift: int, y_shift: int, array_reference: List[List[int]], array_to_be_shifted: List[List[int]]
    ) -> int:
        if x_shift > 0:
            array_to_be_shifted = self.shift_left(array=array_to_be_shifted, shifts=x_shift)
        if y_shift > 0:
            array_to_be_shifted = self.shift_up(array=array_to_be_shifted, shifts=y_shift)

        return self.overlap(array_a=array_reference, array_b=array_to_be_shifted)

    def overlap(self, array_a: List[List[int]], array_b: List[List[int]], value: int = 1) -> int:
        common_values = 0
        for row_a, row_b in zip(array_a, array_b):
            for a, b in zip(row_a, row_b):
                if a == b == value:
                    common_values += 1

        return common_values

    def shift_up(self, array: List[List[int]], shifts: int, fill_value: int = 0) -> List[List[int]]:
        a = array[shifts:]
        for _ in range(shifts):
            a.append([fill_value] * len(array[0]))

        return a

    def shift_left(self, array: List[List[int]], shifts: int, fill_value: int = 0) -> List[List[int]]:
        a = []
        for sublist in array:
            last_elements = [fill_value] * shifts
            sublist = sublist[shifts:] + last_elements
            a.append(sublist)

        return a


#
# @lc app=leetcode id=835 lang=python3
#
# [835] Image Overlap
#

# @lc code=start
from functools import lru_cache

@lru_cache
def countBits(n):
    if n == 0:
        return 0
    return (n & 1) + countBits(n >> 1)

class Solution:
    def stateCompress(self, img):
        n, m = len(img), len(img[0])
        rows = [0 for _ in range(n)]
        for i, row in enumerate(img):
            for j, e in enumerate(row):
                rows[i] = (rows[i] << 1) + e
        return n, m, rows
    
    
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n, m, rA = self.stateCompress(A)
        _, _, rB = self.stateCompress(B)


        def shift(xAs, xAe, xBs, xBe, dy):
            if dy > 0:
                return (countBits((e1 << dy) & e2) for e1, e2 in zip(rA[xAs:xAe], rB[xBs:xBe]))
            else:
                dy = -dy
                return (countBits((e1 >> dy) & e2) for e1, e2 in zip(rA[xAs:xAe], rB[xBs:xBe]))

        print((rA, rB))
        maxOverLap = 0
        for dr in range(n):
            for dc in range(m):
                maxOverLap = max(maxOverLap, sum(shift(dr, n, 0, n - dr, dc)))
                maxOverLap = max(maxOverLap, sum(shift(0, dr, n - dr, n, dc)))
                maxOverLap = max(maxOverLap, sum(shift(dr, n, 0, n - dr, -dc)))
                maxOverLap = max(maxOverLap, sum(shift(0, dr, n - dr, n, -dc)))
        return maxOverLap
                
                
# @lc code=end



#
# @lc app=leetcode id=835 lang=python3
#
# [835] Image Overlap
#

# @lc code=start
from functools import lru_cache

@lru_cache
def countBits(n):
    if n == 0:
        return 0
    return (n & 1) + countBits(n >> 1)

class Solution:
    def stateCompress(self, img):
        n, m = len(img), len(img[0])
        rows = [0 for _ in range(n)]
        for i, row in enumerate(img):
            for j, e in enumerate(row):
                rows[i] = (rows[i] << 1) + e
        return n, m, rows
    
    
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        n, m, rA = self.stateCompress(A)
        _, _, rB = self.stateCompress(B)


        def shift(xAs, xAe, xBs, xBe, dy):
            if dy > 0:
                return sum(countBits((e1 << dy) & e2) for e1, e2 in zip(rA[xAs:xAe], rB[xBs:xBe]))
            else:
                dy = -dy
                return sum(countBits((e1 >> dy) & e2) for e1, e2 in zip(rA[xAs:xAe], rB[xBs:xBe]))

        print((rA, rB))
        maxOverLap = 0
        for dr in range(n):
            for dc in range(m):
                maxOverLap = max(maxOverLap, shift(dr, n, 0, n - dr, dc))
                maxOverLap = max(maxOverLap, shift(0, dr, n - dr, n, dc))
                maxOverLap = max(maxOverLap, shift(dr, n, 0, n - dr, -dc))
                maxOverLap = max(maxOverLap, shift(0, dr, n - dr, n, -dc))
        return maxOverLap
                
                
# @lc code=end



def matrix_to_set(A):
    return {(i, j) for i, row in enumerate(A)
                   for j, pixel in enumerate(row) if pixel}

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        set_a, set_b = matrix_to_set(A), matrix_to_set(B)
        
        if len(set_b) < len(set_a):
            set_b, set_a = set_a, set_b
    
        return max(sum((i + di, j + dj) in set_b for i, j in set_a)
                   for di in range(-N + 1, N)
                   for dj in range(-N + 1, N)) 


class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        N = len(img1)
        if N == 1:
            return 1 if img1[0][0] == 1 and img2[0][0] == 1 else 0
        max_slide = N
        sliders = set()
        for i in range(N):
            for j in range(N):
                sliders.add((i, j))
                sliders.add((-i, j))
                sliders.add((i, -j))
                sliders.add((-i, -j))
        
        def slide_and_count(slide):
            res = 0
            left, down = slide
            for i in range(min(N, N-left)):
                i2 = i + left
                for j in range(min(N, N-down)):
                    j2 = j + down
                    if i2 < 0 or j2 < 0:
                        continue
                    try:
                        if img1[i][j] == 1 and img2[i2][j2] == 1:
                            res += 1
                    except:
                        pass
                    
            print(slide, res)
            return res
        
        return max(slide_and_count(slide) for slide in sliders)

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        return max(self.largestOverlapAtoB(A, B), self.largestOverlapAtoB(B, A))
        
    def largestOverlapAtoB(self, A, B):
        shift_row = 0
        shift_col = 0
        overlap = 0
        for shift_row in range(len(A[0])):
            for shift_col in range(len(A[0])):
                shifted_A = self.shiftMatrix(A, shift_row, shift_col)
                overlap = max(overlap, self.findOverlap(B, shifted_A))
        return overlap
        
    def findOverlap(self, A, B):
        lenght = len(A[0])
        overlap = 0
        for ii in range(lenght):
            for jj in range(lenght):
                if A[ii][jj] == B[ii][jj] and A[ii][jj] == 1:
                    overlap += 1
        return overlap
    
    def shiftMatrix(self, M, shift_row, shift_col):
        lenght = len(M[0])
        out = []
        for _ in range(shift_row):
            out.append(lenght * [0])
        for ix_r in range(shift_row, lenght):
            out_row = []
            for _ in range(shift_col):
                out_row.append(0)
            for ix_c in range(shift_col, lenght):
                out_row.append(M[ix_r - shift_row][ix_c - shift_col])
                
            out.append(out_row)
        
        return out
                    
                    



def check_overlap(side, down, A, B):
    overlap = 0
    for i in range(len(A)):
        for j in range(len(A)):
            try:
                overlap += A[i+side][j+down] & B[i][j]
            except:
                pass
            
    return overlap

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        max_overlap = 0
        for i in range(len(A)):
            for j in range(len(A)):
                max_overlap = max(max_overlap, check_overlap(i, j, A, B))
                max_overlap = max(max_overlap, check_overlap(i, j, B, A))
                
        return max_overlap

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        def check_overlap(side_x, down_x, A, B):# A is shifted
            overlap = 0
            for i in range(len(A)):
                for j in range(len(A)):
                    try:
                        overlap += A[i+side_x][j+down_x] & B[i][j]
                    except:
                        pass
            
            return overlap
        
        max_overlap = 0
        for i in range(len(A)):
            for j in range(len(A)):
                max_overlap = max(max_overlap, check_overlap(i, j, A, B))
                max_overlap = max(max_overlap, check_overlap(i, j, B, A))
                
        return max_overlap

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        
        def match(m1, m2):
            prod = 0
            for r1, r2 in zip(m1, m2):
                for v1, v2 in zip(r1, r2):
                    prod += v1 * v2
            return prod
        
        pad = [0] * (3 * (len(A) - 1))
        largeA = [pad] * (len(A) - 1)
        for i in range(len(A)):
            largeA.append([0] * (len(A)-1) + A[i] + [0] * (len(A)-1))
        largeA += [pad] * (len(A) - 1)
        maxProd = 0
        #print(largeA)
        for i in range(len(largeA) - len(A) + 1):
            for j in range(len(largeA) - len(A) + 1):
                subA = []
                for r in largeA[i:len(A) + i]:
                    subA.append(r[j:len(A) + j])
                prod = match(subA, B)
                if prod > maxProd:
                    maxProd = prod
        return maxProd
            
            
                


from typing import List

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        # help function to count overlaps in A (shifted) and B:
        def check_overlap(side_x, down_x, A, B):
            overlap = 0
            for i in range(len(A)):
                for j in range(len(A)):
                    try:
                        overlap += A[i+side_x][j+down_x] & B[i][j]
                    except:
                        pass
            
            return overlap
        
        # try all options:
        max_overlap = 0
        for i in range(len(A)):
            for j in range(len(A)):
                max_overlap = max(max_overlap, check_overlap(i, j, A, B))
                max_overlap = max(max_overlap, check_overlap(i, j, B, A))
                
        return max_overlap

class Solution:
    # Naming assumes row major.
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        # move A through all the valid positions in B's coordinate space.
        a_1_locations = set()
        b_1_locations = set()

        for grid, locations in [ (A, a_1_locations), (B, b_1_locations) ]:
            for i, col in enumerate(grid):
                for j, val in enumerate(col):
                    if val == 1:
                        locations.add((i,j))

        max_overlap = 0
        max_abs_x1_offset = len(A)
        max_abs_x2_offset = len(A[0])
        a_offsets = itertools.product(range(-1 * max_abs_x1_offset, max_abs_x1_offset),
                                      range(-1 * max_abs_x2_offset, max_abs_x2_offset))
        
        for a_offset_x, a_offset_y in a_offsets:
            a_1_locations_offset = set(map( lambda location: (location[0] + a_offset_x, location[1] + a_offset_y),
                                        a_1_locations ))
            overlap = len(a_1_locations_offset & b_1_locations)
            if overlap > max_overlap: max_overlap = overlap

        return max_overlap

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        A = [(i, j) for i, row in enumerate(img1) for j, item in enumerate(row) if item]
        B = [(i, j) for i, row in enumerate(img2) for j, item in enumerate(row) if item]
        count = collections.Counter((ax-bx, ay-by) for ax, ay in A for bx, by in B)
        return max(list(count.values()) or [0])


class Solution:
    def getCoordinate(self, A: List[List[int]]):
        list_a = []
        for i in range(len(A)):
            for j in range(len(A[i])):
                if A[i][j] == 1:
                    list_a.append(i*100 + j)
        return list_a
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        list_a = self.getCoordinate(A)
        list_b = self.getCoordinate(B)
        
        diff = [a - b for a in list_a for b in list_b]
        
        counter = {}
        for v in diff:
            if counter.get(v, None) == None:
                counter[v] = 1
            else:
                counter[v] += 1
        
        max_value = 0
        for key in list(counter.keys()):
            if counter[key] > max_value:
                max_value = counter[key]
        return max_value


class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        index_A = [(i, j) for i, row in enumerate(A) for j, item in enumerate(row) if item]
        index_B = [(i, j) for i, row in enumerate(B) for j, item in enumerate(row) if item]
        
        cnt = collections.Counter([(ax-bx, ay-by)for ax, ay in index_A for bx, by in index_B])
        
        if len(cnt) == 0:
            return 0 
        return max(cnt.values())

class Solution:
    def largestOverlap(self, A, B):
        A = [(i, j) for i, row in enumerate(A) for j, item in enumerate(row) if item]
        B = [(i, j) for i, row in enumerate(B) for j, item in enumerate(row) if item]
        
        count = {}
        for ax, ay in A:
            for bx, by in B:
                delta = (ax-bx, ay-by)
                if not delta in count: count[delta]=0
                count[delta]+=1
        return max(count.values()) if count else 0