835. Image Overlap
Medium
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:
We translate 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 == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j]
is either0
or1
.img2[i][j]
is either0
or1
.
Runtime: 84 ms, faster than 50.00%
Memory Usage: 6.1 MB, less than 50.00%
下方之所以用 i*100+j 來記錄 (x, y) ,而不是用二維陣列或 struct 紀錄是因為題目有限制正方形邊長最大為 30 。
func largestOverlap(img1 [][]int, img2 [][]int) int {
length := len(img1)
arr1 := make([]int, 0)
arr2 := make([]int, 0)
for i:= 0; i<length; i++ {
for j:=0; j<length; j++ {
if img1[i][j]==1 { arr1 = append(arr1, i*100+j) }
if img2[i][j]==1 { arr2 = append(arr2, i*100+j) }
}
}
count := make(map[int]int)
ans := 0
for i:=0; i<len(arr1); i++ {
for j:=0; j<len(arr2); j++ {
count[arr1[i]-arr2[j]]++
if count[arr1[i]-arr2[j]] > ans {
ans = count[arr1[i]-arr2[j]]
}
}
}
return ans
}
Last modified 6mo ago