Image Overlap Solution In C++/Python/java/JS
Problem Description
You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s 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
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).
Input: img1 = [[1]], img2 = [[1]]
Output: 1
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 either 0 or 1.
- img2[i][j] is either 0 or 1.
Figuring out "Image Overlap" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!
Optimal Approach
Intuition
We’re given two n x n binary images — img1 and img2. Each one is made up of 0s and 1s.
Our job?
Slide one of them around in any direction (up, down, left, right) — no rotations though — and place it on top of the other.
Then we check:
“How many 1s overlap — like, they are both 1 at the same position?”
And finally, return the maximum overlap we can achieve from any possible translation.
Let’s Work with a Tiny Example First
To make it digestible, imagine:
img1 = [[1, 0],[0, 0]]
img2 = [[0, 1],[0, 0]]
So:
• img1 has a single 1 at (0, 0)
• img2 has a single 1 at (0, 1)
Now think visually — if we slide img1 one step to the right, the 1 at (0,0) will land at (0,1), right?
And guess what’s there in img2 at (0,1)? Yep — a '1'
So we get 1 overlap!
How Would We Solve This in Code?
First instinct? Maybe we try all possible shifts of img1 across img2, and every time, we count how many overlapping 1s we get.
And that's valid! But it's... kinda expensive.
Let’s say the grid is n x n. We can shift rows from -(n-1) to +(n-1) and same for columns. That’s like O(n²) possible shifts and for each shift, we’d compare O(n²) positions in both images.
So overall we’re doing O(n⁴) work.
But… we’re not giving up yet. Let’s see if we can think smarter.
What Actually Matters?
Think about it. We're not interested in all the zeros. We only care about the 1s in both images.
So what if we:
- Find all positions of 1s in img1
- Find all positions of 1s in img2
- Try to match every 1 from img1 with every 1 from img2
- And for each match attempt, figure out how we’d need to shift img1 to make the two 1s line up
Let’s zoom in on step 4, because here’s where it gets a little tricky.
How Do We Calculate the Required Shift?
Let’s say there’s a 1 in img1 at position (i, j) and there’s a 1 in img2 at position (h, k)
Now — let’s ask:
"What shift would we need to apply to img1, so that the 1 at (i, j) ends up exactly at (h, k)?"
To do that, we’d have to move:
• Rows: from i to h → that’s a difference of h - i
• Columns: from j to k → that’s a difference of k - j
So the required shift is:
row shift = h - i
col shift = k - j
But wait — if we want to shift img1's point (i, j) to (h, k), don't we need to apply that shift in the correct direction?
You’re right — this depends on whether we’re conceptually sliding img1 onto img2, or the other way around.
So to keep things consistent, most solutions (and the one we’ll follow) calculate the shift as:
delta_row = h - i
delta_col = k - j
Why? Because we’re shifting img1, and asking:
“If I want the 1 from (i, j) in img1 to land over the 1 at (h, k) in img2, how far down and right do I need to move?”
A shift of (h - i, k - j) will move img1[i][j] down by (h - i) units and right by (k - j) units, aligning it over img2[h][k].
Let’s Run Through a Better Example
img1 = [[1, 0, 0],
[0, 1, 0],
[0, 0, 0]]
img2 = [[0, 0, 0],
[0, 1, 0],
[0, 0, 1]]
First, gather all 1 positions:
• From img1: (0, 0), (1, 1)
• From img2: (1, 1), (2, 2)
Now, match every 1 from img1 with every 1 from img2 and calculate the shift (delta_row, delta_col) as:
Pairwise Matches:
|
img1 (i, j) |
img2 (h, k) |
Shift = (h - i, k - j) |
Meaning |
|
(0, 0) |
(1, 1) |
(1, 1) |
move down and right |
|
(0, 0) |
(2, 2) |
(2, 2) |
move down twice & right twice |
|
(1, 1) |
(1, 1) |
(0, 0) |
already perfectly aligned |
|
(1, 1) |
(2, 2) |
(1, 1) |
move down and right again |
Now, we’ll keep a count of how many times each shift occurs:
Shift Count:
|
Shift |
Count |
|
(1, 1) |
2 |
|
(2, 2) |
1 |
|
(0, 0) |
1 |
What Does This Shift Count Actually Mean?
This part is super important, especially if you're just starting out with this kind of problem.
Let’s slow down and make sense of what we just did.
We created a map of shifts — like (1, 1), (2, 2), (0, 0) — and counted how often each one occurred.
But what does a shift like (1, 1) actually mean?
It means:
“If we move img1 down by 1 row and right by 1 column, then some 1s in img1 will line up exactly with some 1s in img2 — they’ll overlap!”
Let’s visualize what’s happening when we apply that shift:
• img1[0][0] would move to position [1][1], which aligns with img2[1][1]
• img1[1][1] would move to [2][2], which aligns with img2[2][2]
So under this shift of (1, 1), two 1s from img1 end up sitting on top of two 1s from img2.
That’s why the count for shift (1, 1) is 2 — it gives us 2 overlaps!
Why Are We Counting These Shifts?
Here’s the key idea:
• Every time we match a 1 from img1 with a 1 from img2, we note what shift would make them align.
• If the same shift comes up again for another pair of 1s — great! It means that shift causes more 1s to overlap.
So the shift with the highest count tells us:
“This is the best way to move img1 — it gives the maximum number of overlapping 1s.”
And that’s exactly what the problem is asking us to find.
So instead of brute-forcing every possible movement, we let the 1s tell us what shifts matter and use a hash map to count them efficiently.
Final Takeaway
• We don't shift entire matrices around
• We let the 1s tell us what shifts would work best
• We count those shifts using a hash map
• And return the shift that produces the most overlaps
Well summarized! Now, if you think about it, what kind of approach are we using here?
Without even realizing it, we used something clever — a technique called:
Hash Map Frequency Counting of Translation Vectors.
We didn’t brute-force every possible shift. Instead, we let the matching 1s between the two matrices guide us.
We counted how often each shift happened — and the shift with the highest count?
That’s our winner — the one that gives us maximum overlap.
Let's now see how our algorithm looks!
Image Overlap Algorithm
We implement a maximum image overlap solution using vector translations.
Step 1: Extract Positions of 1s
- Traverse through both img1 and img2.
- Store the positions (i, j) of all 1s in two separate lists:
- ones1 for img1
- ones2 for img2
Step 2: Calculate Translation Vectors
- For every coordinate (x1, y1) in ones1, and every coordinate (x2, y2) in ones2:
- Compute the translation vector (dx, dy) = (x1 - x2, y1 - y2)
- This vector represents the shift needed to align a 1 from img1 with a 1 from img2
Step 3: Use Hash Map to Count Matches
- For each (dx, dy), increment its count in a hash map (dictionary).
- Track the maximum value in the map as you go.
- This tells us how many 1s can overlap using that particular shift.
Step 4: Return Maximum Overlap Count: The result is the highest value in the hash map → maximum overlap of 1s possible with any shift.
Approach
1. Extract Coordinates of 1s: We first collect all coordinates (i, j) where the value is 1 in both img1 and img2. This gives us two lists of positions:
- ones1 for img1
- ones2 for img2
2. Calculate All Translation Vectors
- For every 1 in img1, we compute the vector difference (dx, dy) between it and every 1 in img2.
- This simulates all possible shifts that would align that specific point in img1 with one in img2.
3. Count Overlap Frequencies
- We use a hash map (dictionary) to count how many times each (dx, dy) shift occurs.
- The most frequent shift represents the transformation that results in the maximum overlap.
4. Return the Maximum Count: After processing all pairs, the highest frequency in the map tells us the maximum number of overlapping 1s after some shift.
Let us understand this with a video,
Image Overlap-Optimal-Approach-Animation
Dry-Run
Input:
img1 = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]
img2 = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
Output: 2
Explanation
Step 1: Find positions of all 1s
In img1, positions of 1s:
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
In img2, positions of 1s:
(0, 0)
(1, 1)
(2, 2)
Step 2: Try matching each 1 from img1 with each 1 from img2
We calculate the shift needed to move a 1 from img1 onto a 1 in img2.
Formula: (dx, dy) = (i1 - i2, j1 - j2)
From img1[0][1] = 1
→ match img2[0][0] → (0, 1)
→ match img2[1][1] → (-1, 0)
→ match img2[2][2] → (-2, -1)
From img1[1][0] = 1
→ match img2[0][0] → (1, 0)
→ match img2[1][1] → (0, -1)
→ match img2[2][2] → (-1, -2)
From img1[1][1] = 1
→ match img2[0][0] → (1, 1)
→ match img2[1][1] → (0, 0)
→ match img2[2][2] → (-1, -1)
From img1[1][2] = 1
→ match img2[0][0] → (1, 2)
→ match img2[1][1] → (0, 1)
→ match img2[2][2] → (-1, 0)
From img1[2][1] = 1
→ match img2[0][0] → (2, 1)
→ match img2[1][1] → (1, 0)
→ match img2[2][2] → (0, -1)
Step 3: Count how many times each shift appears
(0, 1) → 2 times
(-1, 0) → 2 times
(-2, -1) → 1 time
(1, 0) → 2 times
(0, -1) → 2 times
(-1, -2) → 1 time
(1, 1) → 1 time
(0, 0) → 1 time
(-1, -1) → 1 time
(1, 2) → 1 time
(2, 1) → 1 time
Step 4: Choose the shift with the highest count. The maximum overlap is 2, from any of these shifts: (0, 1), (-1, 0), (1, 0), (0, -1)
Final Answer: 2
Image Overlap Solution
Now let's checkout the "Image Overlap code" in C++, Java, Python and JavaScript.
"Image Overlap" Code in all Languages.
1. Image Overlap solution in C++ Try on Compiler
class Solution {
public:
// Function to compute the largest overlap between two binary images
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
// Get the size of the images (assuming square matrices)
int n = img1.size();
// Vectors to store the positions of 1s in both images
vector<pair<int, int>> ones1, ones2;
// Collect positions of 1s in img1
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img1[i][j] == 1) {
ones1.emplace_back(i, j);
}
}
}
// Collect positions of 1s in img2
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img2[i][j] == 1) {
ones2.emplace_back(i, j);
}
}
}
// Map to count how many times each vector (deltaX, deltaY) appears
unordered_map<string, int> countMap;
int maxOverlap = 0;
// Compare each 1's position in img1 with each in img2
for (const auto& p1 : ones1) {
for (const auto& p2 : ones2) {
// Calculate the translation vector needed to align p1 with p2
int dx = p1.first - p2.first;
int dy = p1.second - p2.second;
string key = to_string(dx) + "," + to_string(dy);
// Increment the count of this translation vector
countMap[key]++;
// Update the maximum overlap found
maxOverlap = max(maxOverlap, countMap[key]);
}
}
// Return the maximum overlap found
return maxOverlap;
}
};2. Image Overlap Solution in Java Try on Compiler
public class Solution {
// Function to compute the largest overlap between two binary images
public int largestOverlap(int[][] img1, int[][] img2) {
// Get the size of the images (assuming square matrices)
int n = img1.length;
// Lists to store the positions of 1s in both images
List<int[]> ones1 = new ArrayList<>();
List<int[]> ones2 = new ArrayList<>();
// Collect positions of 1s in img1
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img1[i][j] == 1) {
ones1.add(new int[]{i, j});
}
}
}
// Collect positions of 1s in img2
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img2[i][j] == 1) {
ones2.add(new int[]{i, j});
}
}
}
// Map to count how many times each vector (deltaX, deltaY) appears
Map<String, Integer> countMap = new HashMap<>();
int maxOverlap = 0;
// Compare each 1's position in img1 with each in img2
for (int[] p1 : ones1) {
for (int[] p2 : ones2) {
// Calculate the translation vector needed to align p1 with p2
int dx = p1[0] - p2[0];
int dy = p1[1] - p2[1];
String key = dx + "," + dy;
// Increment the count of this translation vector
countMap.put(key, countMap.getOrDefault(key, 0) + 1);
// Update the maximum overlap found
maxOverlap = Math.max(maxOverlap, countMap.get(key));
}
}
// Return the maximum overlap found
return maxOverlap;
}
}3. Image Overlap Solution in Python Try on Compiler
class Solution:
def largestOverlap(self, img1, img2):
# Get the size of the images (they are square)
n = len(img1)
# Lists to store coordinates of 1s in img1 and img2
ones1 = []
ones2 = []
# Collect positions of 1s in img1
for i in range(n):
for j in range(n):
if img1[i][j] == 1:
ones1.append((i, j))
# Collect positions of 1s in img2
for i in range(n):
for j in range(n):
if img2[i][j] == 1:
ones2.append((i, j))
# Dictionary to count how many times each translation vector appears
count_map = {}
max_overlap = 0
# Compare each 1's position in img1 with each in img2
for x1, y1 in ones1:
for x2, y2 in ones2:
# Calculate the translation vector (dx, dy)
dx = x1 - x2
dy = y1 - y2
key = (dx, dy)
# Increment the count for this vector
count_map[key] = count_map.get(key, 0) + 1
# Update max_overlap if needed
max_overlap = max(max_overlap, count_map[key])
# Return the maximum number of overlaps
return max_overlap
4. Image Overlap solution in JavaScript Try on Compiler
/**
* @param {number[][]} img1
* @param {number[][]} img2
* @return {number}
*/
var largestOverlap = function(img1, img2) {
// Get the size of the images (assuming square matrices)
const n = img1.length;
// Arrays to store the positions of 1s in both images
const ones1 = [];
const ones2 = [];
// Collect positions of 1s in img1
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (img1[i][j] === 1) {
ones1.push([i, j]);
}
}
}
// Collect positions of 1s in img2
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (img2[i][j] === 1) {
ones2.push([i, j]);
}
}
}
// Map to count how many times each translation vector appears
const countMap = new Map();
let maxOverlap = 0;
// Compare each 1's position in img1 with each in img2
for (const [x1, y1] of ones1) {
for (const [x2, y2] of ones2) {
// Calculate the translation vector (dx, dy)
const dx = x1 - x2;
const dy = y1 - y2;
const key = `${dx},${dy}`;
// Increment the count of this translation vector
const count = (countMap.get(key) || 0) + 1;
countMap.set(key, count);
// Update the maximum overlap found
maxOverlap = Math.max(maxOverlap, count);
}
}
// Return the maximum overlap found
return maxOverlap;
};Image Overlap Complexity Analysis
Time Complexity: O(n⁴)
The Image Overlap algorithm involves two key operations:
1. Finding all positions of 1s in both images: We iterate through both img1 and img2 to collect coordinates where the value is 1.
Each image is n x n, so this step takes O(n²) time.
2. Calculating all shifts and tracking overlap counts: We compute the vector shift (dx, dy) for every pair of 1s — one from img1, one from img2.
Let’s say:
- k1 = number of 1s in img1
- k2 = number of 1s in img2
This step performs k1 * k2 comparisons, which is at most O(n⁴) in the worst case (if both images are all 1s).
We use a hash map to track frequency of each shift vector, which is a constant-time operation for each pair. So total cost here is also O(k1 * k2).
3. Finding the maximum overlap from the map:
We loop through the map to find the highest frequency shift, which takes O(m) time, where m is the number of unique shifts. In worst case, m ≤ k1 * k2.
Final Time Complexity: O(n² + k1 * k2) → which in worst case is O(n⁴)
Space Complexity: O(k1 * k2)
Auxiliary Space Complexity: Auxiliary space refers to the extra space required by the algorithm other than extra space.
The algorithm uses the following additional data structures:
- Two lists to store positions of 1s from img1 and img2:
→ O(k1 + k2) where k1 and k2 are the number of 1s in each image - One hash map to count shift frequencies:
→ At most O(k1 * k2) entries in the worst case
Thus, auxiliary space complexity is O(k1 * k2)
→ Worst-case when both images are entirely filled with 1s: O(n⁴)
Total Space Complexity
- Input storage (two n × n matrices): O(n²).
- Storing coordinates of 1s: O(k1 + k2)
- Shift count map: O(k1 * k2)
- Constant space for loop variables and tracking max overlap: O(1)
So, total space complexity: O(n² + k1 * k2)
Similar Problems
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.