Image Overlap
01 · Problem
You are given two binary images img1 and img2, each an n x n grid of 0s and 1s.
You may slide img1 by any whole number of cells left, right, up, and/or down, then lay it on top of img2. Rotations and flips are not allowed. Any 1 that slides outside the grid is discarded. The overlap of a placement is the number of positions where both images show a 1.
Return the largest overlap achievable over all translations, including not moving at all. If either image contains no 1, the answer is 0.
02 · Examples
img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
3
Shift img1 one cell right and one cell down. Its 1s at (0,0),(0,1),(1,1) land on (1,1),(1,2),(2,2), all of which are 1 in img2, for an overlap of 3.
img1 = [[1]], img2 = [[1]]
1
With no shift, the single 1s line up.
img1 = [[0]], img2 = [[0]]
0
There are no 1s, so no placement can overlap anything.
03 · Constraints
- 01n == img1.length == img1[i].length
- 02n == img2.length == img2[i].length
- 031 <= n <= 30
- 04img1[i][j] and img2[i][j] are either 0 or 1
04 · Optimal complexity
- Time
- O(n^4)
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.