#835

Image Overlap

specialist · 685 · lc medium +30 · verified · 64% accepted · 1,406 likes · top 67%

Description

You are given two binary square matrices, img1 and img2, each of size n x n. A binary matrix contains only 0s and 1s.

You may translate img1 by sliding all of its 1-bits in any direction (left, right, up, or down) by any number of steps, then overlay it on top of img2. The overlap count is the number of positions where both matrices have a 1. Bits that slide outside the matrix boundaries are discarded.

Rotation is not allowed. Return the maximum overlap achievable.

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 translate img1 to right by 1 unit and down by 1 unit.

Example 2:

The number of positions that have a 1 in both images is 3 (shown in red).

Example 3:

Input: img1 = [[1]], img2 = [[1]]

Output: 1

Example 4:

Input: img1 = [[0]], img2 = [[0]]

Output: 0

Code

1

2

3

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

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