Image Overlap — Solution in Python, Java & C++
Image Overlap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.
Image Overlap is a medium coding problem on arrays, matrix and enumeration, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Enumeration
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
img1 and img2 are two binary images, each an n x n matrix of 0s and 1s.
You may translate img1 — slide it any number of cells left, right, up and/or down (no rotation) — and then lay it over img2. Cells that slide outside the n x n frame are dropped. The overlap is the number of positions where both images hold a 1.
Return the largest overlap over every possible translation.
Example 1
Input: img1 = [[1,1,0],[0,1,0],[0,0,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: Slide `img1` one cell right and one cell down: all three of its 1s land on 1s of `img2`.
Example 2
Input: img1 = [[1,0],[1,1]], img2 = [[1,1],[0,1]]
Output: 2
Example 3
Input: img1 = [[0]], img2 = [[0]]
Output: 0
Constraints
n == img1.length == img1[i].lengthn == img2.length == img2[i].length1 <= n <= 30img1[i][j] is 0 or 1img2[i][j] is 0 or 1
Hints for Image Overlap
Hint 1
A translation is a vector
(dr, dc)with each component between-(n-1)andn-1.Hint 2
A 1 at
(i, j)inimg1and a 1 at(r, c)inimg2line up under exactly one translation:(r - i, c - j).Hint 3
Pair every 1 of
img1with every 1 ofimg2, count how often each translation vector occurs, and return the largest count.
How to solve Image Overlap
Instead of trying every shift and counting overlaps, let each pair of 1s vote for the single shift that aligns them; the most-voted shift is the answer and its vote count is the overlap.
Approach
- List the coordinates of the 1s in
img1and inimg2. - For every pair (one from each list), compute
(r - i + n - 1, c - j + n - 1)and increment that cell of a(2n-1) × (2n-1)counter. - Return the largest counter value (0 if either image has no 1s).
Why it works
Under translation (dr, dc) the overlap is the number of 1s (i, j) of img1 whose shifted position (i + dr, j + dc) is a 1 of img2 — exactly the number of pairs that voted for (dr, dc). A shifted cell that leaves the frame cannot hit a 1 of img2, so the dropped cells never cast votes.
Complexity
- Time —
O(n⁴) in the worst case (all ones), typically much less - Space —
O(n²)
Pitfalls
- Shifts are in both directions — negative offsets matter as much as positive ones.
- Offset the vector by
n - 1before using it as an array index. - The images are not wrapped around; cells pushed out of the frame are lost.
Reference solution
Python
from typing import List
def largestOverlap(img1: List[List[int]], img2: List[List[int]]) -> int:
n = len(img1)
a = [(i, j) for i in range(n) for j in range(n) if img1[i][j] == 1]
b = [(i, j) for i in range(n) for j in range(n) if img2[i][j] == 1]
size = 2 * n - 1
count = [0] * (size * size)
best = 0
for ai, aj in a:
for bi, bj in b:
k = (bi - ai + n - 1) * size + (bj - aj + n - 1)
count[k] += 1
if count[k] > best:
best = count[k]
return bestJava
public static int largestOverlap(int[][] img1, int[][] img2) {
int n = img1.length, size = 2 * n - 1;
List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (img1[i][j] == 1) a.add(new int[]{i, j});
if (img2[i][j] == 1) b.add(new int[]{i, j});
}
}
int[] count = new int[size * size];
int best = 0;
for (int[] p : a) {
for (int[] q : b) {
int k = (q[0] - p[0] + n - 1) * size + (q[1] - p[1] + n - 1);
if (++count[k] > best) best = count[k];
}
}
return best;
}C++
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int n = img1.size(), size = 2 * n - 1;
vector<pair<int, int>> a, b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (img1[i][j] == 1) a.push_back({i, j});
if (img2[i][j] == 1) b.push_back({i, j});
}
}
vector<int> count(size * size, 0);
int best = 0;
for (auto& p : a) {
for (auto& q : b) {
int k = (q.first - p.first + n - 1) * size + (q.second - p.second + n - 1);
best = max(best, ++count[k]);
}
}
return best;
}JavaScript
var largestOverlap = function(img1, img2) {
var n = img1.length, size = 2 * n - 1;
var ar = [], ac = [], br = [], bc = [];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
if (img1[i][j] === 1) { ar.push(i); ac.push(j); }
if (img2[i][j] === 1) { br.push(i); bc.push(j); }
}
}
var count = new Array(size * size).fill(0), best = 0;
for (var x = 0; x < ar.length; x++) {
for (var y = 0; y < br.length; y++) {
var k = (br[y] - ar[x] + n - 1) * size + (bc[y] - ac[x] + n - 1);
count[k]++;
if (count[k] > best) best = count[k];
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal