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 either 0 or 1.img2[i][j] is either 0 or 1.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.
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.
The C code defines two functions, overlapCount and largestOverlap. overlapCount calculates the number of overlapping 1s given a shift, while largestOverlap tries all possible x and y shifts, keeps track of the maximum overlap, and returns the result. The main function initializes the images and prints the maximum overlap.
Time Complexity: O(n^4), where n is the size of the matrix, due to the two nested loops and a cross-sectional overlap check for each.
Space Complexity: O(1), since the solution uses constant space apart from input storage.
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.
The C convolution solution approaches the problem by varying the shift on rows and columns and utilizes cumulative positions of 1s. It identifies maximum overlap within those defined indices by focusing on particular shifts and computing resulting overlaps without directly shifting matrices.
Time Complexity: O(n^4), as it traverses through each overlap position and checks all cells.
Space Complexity: O(n), due to the allocation of cumulative arrays.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Solution Using Translation | Time Complexity: O(n^4), where n is the size of the matrix, due to the two nested loops and a cross-sectional overlap check for each. Space Complexity: O(1), since the solution uses constant space apart from input storage. |
| Using Convolution | Time Complexity: O(n^4), as it traverses through each overlap position and checks all cells. Space Complexity: O(n), due to the allocation of cumulative arrays. |
| Enumeration | — |
| 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 |
image overlap | image overlap leetcode | leetcode 835 | matrix • Naresh Gupta • 8,870 views views
Watch 9 more video solutions →Practice Image Overlap with our built-in code editor and test cases.
Practice on FleetCode