835. Image Overlap
Problem Description
The problem presents us with two binary square matrices, img1
and img2
, each containing only 0's and 1's. Our task is to determine the largest overlap between these two images when one image is translated (slid in any direction) over the other. The overlap is quantified by counting the number of positions where both images have a 1. A key constraint is that rotation is not allowed, and any 1's that move outside the matrix bounds are discarded. Our goal is to find the maximum overlap after trying all possible translations.
Intuition
To solve this problem, we should think about how to track the overlap between the two images effectively. One way to do this is to consider each 1
in img1
and match it against each 1
in img2
. For each pairing, we can calculate the translation vector (the difference in x and y coordinates) required to move the 1
from img1
directly onto the 1
in img2
.
We approach the solution by iterating over all elements of img1
and img2
. For each 1
we find in img1
, we iterate through img2
, and for every 1
in img2
, we calculate the translation vector. This vector is represented as a tuple (delta_row, delta_col), where delta_row
is the difference in the row indices and delta_col
is the difference in the column indices between a 1
in img1
and a 1
in img2
.
All these vectors are stored in a counter (a dictionary with tuples as keys and their counts as values), which is used to count how many times each vector occurs. The highest count in this counter, after considering all pairs of 1
bits, would represent the most overlapping translation, giving us the largest possible overlap between img1
and img2
.
The solution makes use of the Counter
class from Python's collections module to conveniently keep track of the number of overlaps for each translation vector.
Solution Approach
The provided solution employs a brute-force approach, utilizing nested loops to iterate through each element of both img1
and img2
. Here's a step-by-step explanation:
-
We start by obtaining the size of the given images
n
, assuming both images are of sizen x n
. -
We create a
Counter
from thecollections
module to keep track of all translation vectors and how frequently they result in an overlap. A translation vector is represented as a tuple(delta_i, delta_j)
, which corresponds to the difference in rows (delta_i
) and columns (delta_j
) needed to align a1
fromimg1
with a1
fromimg2
. -
We then proceed with four nested loops:
-
The outer two loops iterate over all the cells of
img1
:- For each position
(i, j)
inimg1
that contains a1
, we then iterate over every position inimg2
using two more loops.
- For each position
-
The inner two loops iterate over all the cells of
img2
:- For each position
(h, k)
inimg2
that contains a1
, we calculate the translation vector needed to move the1
from(i, j)
inimg1
to(h, k)
inimg2
.
- For each position
-
-
The calculated translation vector
(i - h, j - k)
is then used to increment the count in ourCounter
. This effectively counts how many1
bits fromimg1
would overlap with1
bits inimg2
whenimg1
is translated according to this vector. -
After evaluating all possible pairs of
1
s in both images, we find the maximum count from ourCounter
. This count represents the largest number of overlapping1
s for the best translation. We return this maximum count as the solution.
In the worst case, every element of img1
(which could be a 1
) has to be compared with every element of img2
, leading us to a time complexity of O(n^4)
, where n
is the size of one dimension of the image.
Finally, the last line of the function accounts for the possibility of no overlap at all. If cnt
(our Counter
) remains empty because there are no 1
bits overlapping in any translation, we return 0
. Otherwise, we return the maximum value found in cnt
, which is the result of max(cnt.values())
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example where img1
and img2
are both 3x3 binary matrices:
1img1 = [[1,0,0], 2 [0,1,0], 3 [0,0,0]] 4 5img2 = [[0,0,0], 6 [0,1,0], 7 [0,0,1]]
Now, let's walk through the solution approach:
-
We first identify the size
n
of the square matrices, which in this case is3
. -
We create a
Counter
to keep track of the translation vectors -delta_i
anddelta_j
, which denote the row and column differences, respectively. -
Then, we iterate over each cell in
img1
:- For cell
(0,0)
inimg1
, which contains a1
, we check every cell inimg2
. Only cells(1,1)
and(2,2)
contain a1
inimg2
.
- For cell
-
For each
1
inimg2
, we calculate the translation vectors necessary to overlap this1
with the1
at(0,0)
inimg1
:- To overlap
(0,0)
fromimg1
onto(1,1)
inimg2
, we calculate the translation vector as(1 - 0, 1 - 0)
which is(1, 1)
. - To overlap
(0,0)
fromimg1
onto(2,2)
inimg2
, the translation vector is(2 - 0, 2 - 0)
which is(2, 2)
.
- To overlap
-
We add and/or increment the count of these vectors in our
Counter
. -
We repeat steps 3-5 for the other
1
at position(1,1)
inimg1
:- There is one
1
at(1,1)
inimg1
which corresponds directly to the1
at(1,1)
inimg2
. The translation vector in this case is(1 - 1, 1 - 1)
which is(0, 0)
.
- There is one
-
We increment the count of this vector in our
Counter
. Now ourCounter
has counted translation vectors with counts as follows:(1, 1)
: 1 count(2, 2)
: 1 count(0, 0)
: 1 count
-
Finally, we scan through our
Counter
to determine the maximum overlap, which is 1 in this case since each translation only overlaps one1
in both images. The result, therefore, is 1.
So, the largest overlap by translating img1
over img2
or vice versa is a single 1
. The steps above demonstrate the brute-force approach systematically considering all translation vectors and assessing the overlaps.
Solution Implementation
1from typing import List
2from collections import Counter
3
4class Solution:
5 def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
6 # Obtain the size of the square images
7 size = len(A)
8
9 # Initialize a counter to keep track of overlaps
10 overlap_count = Counter()
11
12 # Go through every pixel in first image
13 for i in range(size):
14 for j in range(size):
15 # If we have a 1 (active pixel) in the first image
16 if A[i][j] == 1:
17 # Check against every pixel in the second image
18 for h in range(size):
19 for k in range(size):
20 # If there's a 1 in the same position of the second image
21 if B[h][k] == 1:
22 # Count overlaps by storing the delta (difference) of positions
23 overlap_count[(i - h, j - k)] += 1
24
25 # Find the maximum number of overlaps (if there are any), otherwise return 0
26 return max(overlap_count.values()) if overlap_count else 0
27
1class Solution {
2 public int largestOverlap(int[][] img1, int[][] img2) {
3 int n = img1.length; // dimension of the images
4 // Using a map to store the count of overlaps with particular vector shifts
5 Map<List<Integer>, Integer> shiftCount = new HashMap<>();
6 int maxOverlap = 0; // To track the maximum overlap
7
8 // Iterate through the first image
9 for (int i = 0; i < n; ++i) {
10 for (int j = 0; j < n; ++j) {
11 // Only interested in cells that are 1 (part of the image)
12 if (img1[i][j] == 1) {
13 // Iterate through the second image
14 for (int h = 0; h < n; ++h) {
15 for (int k = 0; k < n; ++k) {
16 // Only interested in cells that are 1 (part of the image)
17 if (img2[h][k] == 1) {
18 // Calculate the vector shift needed to overlay img1's 1 over img2's 1
19 List<Integer> shift = List.of(i - h, j - k);
20 // Using merge to count occurrences of each shift
21 int count = shiftCount.merge(shift, 1, Integer::sum);
22 // Keeping track of the max overlap by comparing and choosing the larger count
23 maxOverlap = Math.max(maxOverlap, count);
24 }
25 }
26 }
27 }
28 }
29 }
30 // Return the max overlap found during iteration
31 return maxOverlap;
32 }
33}
34
1#include <vector>
2#include <map>
3#include <utility>
4#include <algorithm>
5
6class Solution {
7public:
8 int largestOverlap(std::vector<std::vector<int>>& image1, std::vector<std::vector<int>>& image2) {
9 int size = image1.size();
10 std::map<std::pair<int, int>, int> overlapCount; // Holds the count of overlaps per translation vector
11 int maxOverlap = 0; // Keeps track of the maximum overlap count
12
13 // Iterate over all the pixels in image1
14 for (int i = 0; i < size; ++i) {
15 for (int j = 0; j < size; ++j) {
16 // Check if there is an image part at the current pixel in image1
17 if (image1[i][j] == 1) {
18 // Iterate over all the pixels in image2
19 for (int h = 0; h < size; ++h) {
20 for (int k = 0; k < size; ++k) {
21 // Check if there is an image part at the current pixel in image2
22 if (image2[h][k] == 1) {
23 // Calculate the translation vector from the current pixel in image2 to the current pixel in image1
24 std::pair<int, int> translationVector = std::make_pair(i - h, j - k);
25 // Increment the overlap count for this translation vector
26 overlapCount[translationVector]++;
27 // Update the maxOverlap if the current overlap count is greater
28 maxOverlap = std::max(maxOverlap, overlapCount[translationVector]);
29 }
30 }
31 }
32 }
33 }
34 }
35
36 // Return the maximum overlap count found
37 return maxOverlap;
38 }
39};
40
1function largestOverlap(image1: number[][], image2: number[][]): number {
2 // Determine the dimension of the square images
3 const size = image1.length;
4
5 // Create a map to hold the counts of the overlaps
6 const overlapCount: Map<number, number> = new Map();
7
8 // Initialize the maximum number of overlaps to 0
9 let maxOverlap = 0;
10
11 // Iterate through each cell of the first image
12 for (let row1 = 0; row1 < size; ++row1) {
13 for (let col1 = 0; col1 < size; ++col1) {
14 // Proceed if this cell of the first image has a '1'
15 if (image1[row1][col1] === 1) {
16 // Now, iterate through each cell of the second image
17 for (let row2 = 0; row2 < size; ++row2) {
18 for (let col2 = 0; col2 < size; ++col2) {
19 // Look for '1's in the second image to count overlaps
20 if (image2[row2][col2] === 1) {
21 // Calculate the translation vector as a unique key (assuming size < 200)
22 const translationKey = (row1 - row2) * 200 + (col1 - col2);
23
24 // Use the translation key to update and get the count of this overlap
25 const currentCount = (overlapCount.get(translationKey) ?? 0) + 1;
26 overlapCount.set(translationKey, currentCount);
27
28 // Keep track of the max number of overlaps
29 maxOverlap = Math.max(maxOverlap, currentCount);
30 }
31 }
32 }
33 }
34 }
35 }
36
37 // Return the maximum number of overlapping ones
38 return maxOverlap;
39}
40
Time and Space Complexity
The given code snippet is designed to find the largest overlap of two given binary matrices img1
and img2
by shifting img2
in all possible directions. Here is the analysis of its time complexity and space complexity:
Time Complexity
The time complexity of the function is governed by the four nested loops:
- The two outer loops iterate over each cell of the
img1
matrix, resulting inn^2
iterations, wheren
is the length of the matrix side. - The two inner loops iterate over each cell of the
img2
matrix, also resulting inn^2
iterations.
For each '1' in img1
, the inner loops iterate through the entire img2
matrix. In the worst case, this results in n^2
iterations for the '1's in img1
. Combining these factors, the worst-case time complexity is O(n^2 * n^2)
, which simplifies to O(n^4)
.
Space Complexity
The space complexity is determined by the additional space used by the program which is mainly due to the Counter
object used to count the number of overlaps for each shift. The number of different shifts is bounded by the size of the matrix (n * n
), as the possible shifts range from (-n+1, -n+1)
to (n-1, n-1)
.
Therefore, in the worst case, the Counter
could have up to n^2
entries if every possible shift occurs at least once. Thus, the space complexity is O(n^2)
.
In summary, the time complexity of the code is O(n^4)
and the space complexity is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.