Image Overlap solution and explanation
Google
9 more videos on this problem
Image Overlap | Easy Explanation | Leetcode 835 | codestorywithMIKcodestorywithMIK · 28:56 · 9K views
image overlap | image overlap leetcode | leetcode 835 | matrixNaresh Gupta · 10:24 · 8K views
Image Overlap | LeetCode 835 | C++, Java, PythonKnowledge Center · 21:44 · 8K views
Leetcode - Image Overlap (Python)Timothy H Chang · 6:37 · 3K views
Image Overlap | Leet code 835 | Theory explained + Python codeSai Anish Malla · 17:37 · 2K views
Image Overlap | Leetcode September Challenge (Day6) | Leetcode 835Coding Decoded · 11:27 · 1K views
Daily Leetcode #940: Oct 27, 2022 - 835. Image OverlapProgramming Live with Larry · 16:58 · 1K views
Daily Leetcode #159: Sep 06, 2020 - 835. Image OverlapProgramming Live with Larry · 8:11 · 1K views
Image Overlap Leetcode | Leetcode 835 | Leetcode September ChallengeCode Bashers · 15:32 · 802 views
Image Overlap | LeetCode 835 | Java Explained w/ Code | @LearnOverflowLearn Overflow · 13:25 · 673 views
The problem
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 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].lengthn == img2.length == img2[i].length1 <= n <= 30img1[i][j]is either0or1.img2[i][j]is either0or1.
Approach overview
Problem Overview: You are given two n x n binary matrices representing images. You can translate one image in any direction (up, down, left, right). The goal is to find the maximum number of positions where both images contain 1 after a translation. Only overlapping cells count.
Approach 1: Brute Force Using Translation (Time: O(n^4), Space: O(1))
Try every possible shift of img1 relative to img2. For an n x n grid there are (2n-1)^2 possible translations. For each translation, iterate through the overlapping region and count positions where both matrices contain 1. Track the maximum overlap seen so far. The logic is straightforward: nested loops generate shifts, then another scan compares cells in the overlapping window. This approach relies purely on iteration over the array and matrix structure.
The downside is the cost of checking every translation. Each shift requires scanning up to n^2 cells, producing a total complexity of O(n^4). With the constraint n ≤ 30, this still runs comfortably in practice and is often the first solution implemented during interviews to confirm correctness.
Approach 2: Using Convolution / Cross-Correlation (Time: O(n^2 log n), Space: O(n^2))
The overlap operation is equivalent to computing the cross-correlation of the two binary matrices. Treat each matrix as a signal and compute how well one aligns with the other at every possible shift. This can be implemented using 2D convolution where one matrix is flipped and convolved with the other. Fast Fourier Transform (FFT) accelerates this process.
The key insight: convolution automatically evaluates overlap counts for every translation simultaneously. Convert both matrices into numeric grids, perform FFT-based convolution, and read the maximum value in the result grid. That value represents the maximum number of overlapping 1s. FFT reduces the computation from checking every shift manually to performing polynomial-style multiplication in the frequency domain.
This technique is common in image processing and signal analysis problems involving matrix alignment or pattern matching. It requires additional memory for frequency-domain arrays but significantly reduces runtime compared to brute-force enumeration.
Recommended for interviews: Start with the brute-force translation approach. It clearly demonstrates understanding of how image shifts affect overlap and is easy to implement under pressure. Once correctness is established, discuss convolution or correlation-based optimization. Interviewers typically expect the translation solution first, while recognizing convolution shows deeper algorithmic and mathematical awareness.
Approach 1: Brute Force Solution Using Translation
This solution involves shifting one image over another in all possible positions and counting how many ones overlap. By varying the horizontal and vertical shifts, and calculating overlaps with respect to the position of img2, the solution finds the maximum overlap. This approach iterates over all possible translations, moving img1 relative to img2 and keeping track of the maximum overlap seen.
def largestOverlap(img1, img2):
def overlap_count(xShift, yShift):
n = len(img1)
count = 0
for r in range(n):
for c in range(n):
if 0 <= r + xShift < n and 0 <= c + yShift < n:
count += img1[r][c] & img2[r + xShift][c + yShift]
return count
n = len(img1)
max_overlap = 0
for xShift in range(-n + 1, n):
for yShift in range(-n + 1, n):
max_overlap = max(max_overlap, overlap_count(xShift, yShift))
return max_overlap
img1 = [[1,1,0],[0,1,0],[0,1,0]]
img2 = [[0,0,0],[0,1,1],[0,0,1]]
print("Max Overlap:", largestOverlap(img1, img2))import java.util.*;
public class ImageOverlap {
public static int largestOverlap(int[][] img1, int[][] img2) {
int n = img1.length;
int maxOverlap = 0;
for (int xShift = -n + 1; xShift < n; ++xShift) {
for (int yShift = -n + 1; yShift < n; ++yShift) {
maxOverlap = Math.max(maxOverlap, overlapCount(img1, img2, xShift, yShift));
}
}
return maxOverlap;
}
private static int overlapCount(int[][] img1, int[][] img2, int xShift, int yShift) {
int n = img1.length, count = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
if ((r + xShift >= 0 && r + xShift < n) && (c + yShift >= 0 && c + yShift < n)) {
count += img1[r][c] & img2[r + xShift][c + yShift];
}
}
}
return count;
}
public static void main(String[] args) {
int[][] img1 = {{1, 1, 0}, {0, 1, 0}, {0, 1, 0}};
int[][] img2 = {{0, 0, 0}, {0, 1, 1}, {0, 0, 1}};
System.out.println("Max Overlap: " + largestOverlap(img1, img2));
}
}#include <iostream>
#include <vector>
using namespace std;
int overlapCount(const vector<vector<int>>& img1, const vector<vector<int>>& img2, int xShift, int yShift) {
int n = img1.size(), count = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
if ((r + xShift >= 0 && r + xShift < n) && (c + yShift >= 0 && c + yShift < n)) {
count += img1[r][c] & img2[r + xShift][c + yShift];
}
}
}
return count;
}
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int n = img1.size(), maxOverlap = 0;
for (int xShift = -n + 1; xShift < n; ++xShift) {
for (int yShift = -n + 1; yShift < n; ++yShift) {
int overlap = overlapCount(img1, img2, xShift, yShift);
maxOverlap = max(maxOverlap, overlap);
}
}
return maxOverlap;
}
int main() {
vector<vector<int>> img1 = {{1, 1, 0}, {0, 1, 0}, {0, 1, 0}};
vector<vector<int>> img2 = {{0, 0, 0}, {0, 1, 1}, {0, 0, 1}};
cout << "Max Overlap: " << largestOverlap(img1, img2) << endl;
return 0;
}function largestOverlap(img1, img2) {
function overlapCount(xShift, yShift) {
let n = img1.length, count = 0;
for (let r = 0; r < n; ++r) {
for (let c = 0; c < n; ++c) {
if ((r + xShift >= 0 && r + xShift < n) && (c + yShift >= 0 && c + yShift < n)) {
count += img1[r][c] & img2[r + xShift][c + yShift];
}
}
}
return count;
}
let n = img1.length, maxOverlap = 0;
for (let xShift = -n + 1; xShift < n; ++xShift) {
for (let yShift = -n + 1; yShift < n; ++yShift) {
maxOverlap = Math.max(maxOverlap, overlapCount(xShift, yShift));
}
}
return maxOverlap;
}
const img1 = [[1,1,0],[0,1,0],[0,1,0]];
const img2 = [[0,0,0],[0,1,1],[0,0,1]];
console.log("Max Overlap:", largestOverlap(img1, img2));#include <stdio.h>
#include <stdlib.h>
int overlapCount(int** img1, int** img2, int xShift, int yShift, int n) {
int count = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
if ((r + xShift >= 0 && r + xShift < n) && (c + yShift >= 0 && c + yShift < n)) {
count += img1[r][c] & img2[r + xShift][c + yShift];
}
}
}
return count;
}
int largestOverlap(int** img1, int** img2, int n) {
int maxOverlap = 0;
for (int xShift = -n + 1; xShift < n; ++xShift) {
for (int yShift = -n + 1; yShift < n; ++yShift) {
int overlap = overlapCount(img1, img2, xShift, yShift, n);
maxOverlap = maxOverlap > overlap ? maxOverlap : overlap;
}
}
return maxOverlap;
}
int main() {
int* img1[] = {(int[]){1, 1, 0}, (int[]){0, 1, 0}, (int[]){0, 1, 0}};
int* img2[] = {(int[]){0, 0, 0}, (int[]){0, 1, 1}, (int[]){0, 0, 1}};
int size = 3;
printf("Max Overlap: %d\n", largestOverlap(img1, img2, size));
return 0;
}using System;
class Program {
static void Main() {
int[,] img1 = { {1, 1, 0}, {0, 1, 0}, {0, 1, 0} };
int[,] img2 = { {0, 0, 0}, {0, 1, 1}, {0, 0, 1} };
Console.WriteLine("Max Overlap: " + LargestOverlap(img1, img2));
}
public static int LargestOverlap(int[,] img1, int[,] img2) {
int n = img1.GetLength(0);
int maxOverlap = 0;
for (int xShift = -n + 1; xShift < n; ++xShift) {
for (int yShift = -n + 1; yShift < n; ++yShift) {
maxOverlap = Math.Max(maxOverlap, OverlapCount(img1, img2, xShift, yShift));
}
}
return maxOverlap;
}
private static int OverlapCount(int[,] img1, int[,] img2, int xShift, int yShift) {
int n = img1.GetLength(0), count = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
if ((r + xShift >= 0 && r + xShift < n) && (c + yShift >= 0 && c + yShift < n)) {
count += img1[r, c] & img2[r + xShift, c + yShift];
}
}
}
return count;
}
}In the Python implementation, we define an inner function overlap_count that calculates overlapping 1s for shifts. The main logic consists of nested loops attempting all possible shifts and updating the maximum overlap counter. The result outputs through a print statement call.
Time Complexity: O(n^4), since we iterate over possible shifts and calculate overlap.
Space Complexity: O(1), similar to previous solutions, using constant space outside inputs.
Approach 2: Using Convolution
This solution uses the concept of convolution by considering the images as arrays of points. We tallied the number of overlapping 1s for each relative translation using convolution properties without directly shifting arrays and used efficient matrix operations to compute overlaps.
def largestOverlapConvolution(img1, img2):
from collections import defaultdict
n = len(img1)
a_ones = [(r, c) for r in range(n) for c in range(n) if img1[r][c] == 1]
b_ones = [(r, c) for r in range(n) for c in range(n) if img2[r][c] == 1]
count = defaultdict(int)
max_overlap = 0
for ax, ay in a_ones:
for bx, by in b_ones:
shift = (ax - bx, ay - by)
count[shift] += 1
max_overlap = max(max_overlap, count[shift])
return max_overlap
img1 = [[1, 1, 0], [0, 1, 0], [0, 1, 0]]
img2 = [[0, 0, 0], [0, 1, 1], [0, 0, 1]]
print("Max Overlap Convolution:", largestOverlapConvolution(img1, img2))import java.util.*;
public class ImageOverlap {
public static int largestOverlapConvolution(int[][] img1, int[][] img2) {
int n = img1.length;
List<int[]> aOnes = new ArrayList<>();
List<int[]> bOnes = new ArrayList<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img1[i][j] == 1) aOnes.add(new int[]{i, j});
if (img2[i][j] == 1) bOnes.add(new int[]{i, j});
}
}
Map<String, Integer> count = new HashMap<>();
int maxOverlap = 0;
for (int[] a : aOnes) {
for (int[] b : bOnes) {
String shift = (a[0] - b[0]) + "," + (a[1] - b[1]);
count.put(shift, count.getOrDefault(shift, 0) + 1);
maxOverlap = Math.max(maxOverlap, count.get(shift));
}
}
return maxOverlap;
}
public static void main(String[] args) {
int[][] img1 = {{1, 1, 0}, {0, 1, 0}, {0, 1, 0}};
int[][] img2 = {{0, 0, 0}, {0, 1, 1}, {0, 0, 1}};
System.out.println("Max Overlap Convolution: " + largestOverlapConvolution(img1, img2));
}
}#include <vector>
#include <unordered_map>
using namespace std;
int largestOverlapConvolution(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int n = img1.size();
vector<pair<int, int>> aOnes, bOnes;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img1[i][j] == 1) aOnes.emplace_back(i, j);
if (img2[i][j] == 1) bOnes.emplace_back(i, j);
}
}
unordered_map<string, int> count;
int maxOverlap = 0;
for (auto &[ax, ay] : aOnes) {
for (auto &[bx, by] : bOnes) {
string shift = to_string(ax - bx) + "," + to_string(ay - by);
int overlapCount = ++count[shift];
maxOverlap = max(maxOverlap, overlapCount);
}
}
return maxOverlap;
}
int main() {
vector<vector<int>> img1 = {{1, 1, 0}, {0, 1, 0}, {0, 1, 0}};
vector<vector<int>> img2 = {{0, 0, 0}, {0, 1, 1}, {0, 0, 1}};
printf("Max Overlap Convolution: %d\n", largestOverlapConvolution(img1, img2));
return 0;
}function largestOverlapConvolution(img1, img2) {
const n = img1.length;
const aOnes = [];
const bOnes = [];
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (img1[r][c] === 1) aOnes.push([r, c]);
if (img2[r][c] === 1) bOnes.push([r, c]);
}
}
const count = new Map();
let maxOverlap = 0;
for (const [ax, ay] of aOnes) {
for (const [bx, by] of bOnes) {
const shift = `${ax - bx},${ay - by}`;
count.set(shift, (count.get(shift) || 0) + 1);
maxOverlap = Math.max(maxOverlap, count.get(shift));
}
}
return maxOverlap;
}
const img1 = [[1, 1, 0], [0, 1, 0], [0, 1, 0]];
const img2 = [[0, 0, 0], [0, 1, 1], [0, 0, 1]];
console.log("Max Overlap Convolution:", largestOverlapConvolution(img1, img2));#include <stdio.h>
#include <stdlib.h>
int convolution(int aCumRow[], int aCumCol[], int aRow, int aCol, int* b[], int n) {
int overlapCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int rowIndex = i + aRow - aCumRow[i];
int colIndex = j + aCol - aCumCol[j];
if (rowIndex >= 0 && rowIndex < n && colIndex >= 0 && colIndex < n) {
overlapCount += b[rowIndex][colIndex];
}
}
}
return overlapCount;
}
int largestOverlapConvolution(int* img1[], int* img2[], int n) {
int maxOverlap = 0;
// Represents shifts in row and column indices
int* aCumRow = (int*)calloc(n, sizeof(int));
int* aCumCol = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (img1[i][j] == 1) {
maxOverlap = fmax(maxOverlap, convolution(aCumRow, aCumCol, i, j, img2, n));
}
}
}
free(aCumRow);
free(aCumCol);
return maxOverlap;
}
int main() {
int* img1[] = {(int[]){1, 1, 0}, (int[]){0, 1, 0}, (int[]){0, 1, 0}};
int* img2[] = {(int[]){0, 0, 0}, (int[]){0, 1, 1}, (int[]){0, 0, 1}};
printf("Max Overlap Convolution: %d\n", largestOverlapConvolution(img1, img2, 3));
return 0;
}using System;
using System.Collections.Generic;
public class ImageOverlap {
public static int LargestOverlapConvolution(int[,] img1, int[,] img2) {
int n = img1.GetLength(0);
var aOnes = new List<ValueTuple<int, int>>();
var bOnes = new List<ValueTuple<int, int>>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img1[i, j] == 1) aOnes.Add((i, j));
if (img2[i, j] == 1) bOnes.Add((i, j));
}
}
var count = new Dictionary<string, int>();
int maxOverlap = 0;
foreach (var (ax, ay) in aOnes) {
foreach (var (bx, by) in bOnes) {
string shift = (ax - bx) + "," + (ay - by);
if (!count.ContainsKey(shift)) count[shift] = 0;
count[shift]++;
maxOverlap = Math.Max(maxOverlap, count[shift]);
}
}
return maxOverlap;
}
public static void Main() {
int[,] img1 = { { 1, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 } };
int[,] img2 = { { 0, 0, 0 }, { 0, 1, 1 }, { 0, 0, 1 } };
Console.WriteLine("Max Overlap Convolution: " + LargestOverlapConvolution(img1, img2));
}
}The Python solution moves towards collecting shifted positions of 1s using tuples. By focusing solely on these keys in a defaultdict, tracking maximum deduced overlaps results in efficient calculation.
Time Complexity: O(n^2), with an algorithm centered on count-concentration where 1s congregate.
Space Complexity: O(n^2) from hashmap usage to store translation information.
Approach 3: Enumeration
We can enumerate each position of 1 in img1 and img2, denoted as (i, j) and (h, k) respectively. Then we calculate the offset (i - h, j - k), denoted as (dx, dy), and use a hash table cnt to record the number of occurrences of each offset. Finally, we traverse the hash table cnt to find the offset that appears the most, which is the answer.
The time complexity is O(n^4), and the space complexity is O(n^2), where n is the side length of img1.
function largestOverlap(img1: number[][], img2: number[][]): number {
const n = img1.length;
const cnt: Map<number, number> = new Map();
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (img1[i][j] === 1) {
for (let h = 0; h < n; ++h) {
for (let k = 0; k < n; ++k) {
if (img2[h][k] === 1) {
const t = (i - h) * 200 + (j - k);
cnt.set(t, (cnt.get(t) ?? 0) + 1);
ans = Math.max(ans, cnt.get(t)!);
}
}
}
}
}
}
return ans;
}func largestOverlap(img1 [][]int, img2 [][]int) (ans int) {
type pair struct{ x, y int }
cnt := map[pair]int{}
for i, row1 := range img1 {
for j, x1 := range row1 {
if x1 == 1 {
for h, row2 := range img2 {
for k, x2 := range row2 {
if x2 == 1 {
t := pair{i - h, j - k}
cnt[t]++
ans = max(ans, cnt[t])
}
}
}
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Solution Using Translation | Time Complexity: O(n^4), since we iterate over possible shifts and calculate overlap. Space Complexity: O(1), similar to previous solutions, using constant space outside inputs. |
| Using Convolution | Time Complexity: O(n^2), with an algorithm centered on count-concentration where 1s congregate. Space Complexity: O(n^2) from hashmap usage to store translation information. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Translation | O(n^4) | O(1) | Best for clarity and interviews when n is small (≤30) |
| Convolution / Cross-Correlation (FFT) | O(n^2 log n) | O(n^2) | When optimizing overlap computation or dealing with larger image sizes |
Frequently asked questions
Is Image Overlap easy or hard?
Image Overlap is considered a Medium difficulty problem. The brute-force translation logic is simple, but recognizing the relationship to convolution or cross-correlation requires stronger algorithmic insight.
Image Overlap Python/Java solution
The problem can be implemented easily in Python, Java, C++, JavaScript, C#, and C. The brute-force solution uses nested loops to simulate translations, while optimized implementations may use numerical libraries or custom FFT code to compute convolution.
How to solve Image Overlap in O(n^2 log n)?
Use 2D convolution via Fast Fourier Transform. Treat the matrices as numeric grids, flip one matrix, and compute cross-correlation using FFT multiplication. The resulting matrix stores overlap counts for every translation, and the maximum value gives the answer.
What is the best approach for Image Overlap?
The most common interview solution is brute-force translation. Shift one matrix relative to the other in all possible directions and count overlapping 1s for each shift. This runs in O(n^4) time with O(1) space and works well because the matrix size is small. For more advanced optimization, convolution or cross-correlation can compute all overlaps in O(n^2 log n).
Is Image Overlap asked at Google/Amazon/Meta?
Matrix alignment and grid translation problems similar to Image Overlap appear in interviews at companies like Amazon, Google, and Meta. They test understanding of matrix traversal, coordinate shifting, and optimization strategies such as convolution or hashing translations.
What data structure is used in Image Overlap?
The problem primarily uses 2D arrays (matrices). The brute-force solution relies on nested iteration across matrix coordinates, while optimized variants may use frequency arrays or FFT buffers for convolution-based computation.
What is the time complexity of Image Overlap?
The straightforward translation approach takes O(n^4) time because there are O(n^2) possible shifts and each shift checks up to O(n^2) cells. An optimized convolution-based solution using FFT reduces the complexity to O(n^2 log n) while using O(n^2) additional space.