Loading problem…
You are given two images, `img1` and `img2`, represented as binary, square matrices of size `n x n`. A binary matrix has only `0`s and `1`s as values. We translate one image however we choose by sliding all the `1` bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a `1` in both images. Note also that a translation does not include any kind of rotation. Any `1` bits that are translated outside of the matrix borders are erased. Return 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: Slide img1 right 1 and down 1: three 1-cells land on 1-cells of img2, so the offset (1,1) has 3 votes.
Example 2
Input: img1 = [[1]], img2 = [[1]]
Output: 1
Explanation: Both single cells are 1; the zero offset overlaps them.
Example 3
Input: img1 = [[0]], img2 = [[0]]
Output: 0
Explanation: No 1-cells in either image, so nothing can overlap.
A translation is fully described by a single vector. Every 1 in img1 paired with a 1 in img2 votes for one translation vector; the vector with the most votes is the best overlap.
Run checks all cases above. Submit evaluates all test cases.