835. Image Overlap

MediumArrayMatrix
Leetcode Link

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:

  1. We start by obtaining the size of the given images n, assuming both images are of size n x n.

  2. We create a Counter from the collections 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 a 1 from img1 with a 1 from img2.

  3. We then proceed with four nested loops:

    • The outer two loops iterate over all the cells of img1:

      • For each position (i, j) in img1 that contains a 1, we then iterate over every position in img2 using two more loops.
    • The inner two loops iterate over all the cells of img2:

      • For each position (h, k) in img2 that contains a 1, we calculate the translation vector needed to move the 1 from (i, j) in img1 to (h, k) in img2.
  4. The calculated translation vector (i - h, j - k) is then used to increment the count in our Counter. This effectively counts how many 1 bits from img1 would overlap with 1 bits in img2 when img1 is translated according to this vector.

  5. After evaluating all possible pairs of 1s in both images, we find the maximum count from our Counter. This count represents the largest number of overlapping 1s 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 Evaluator

Example 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:

  1. We first identify the size n of the square matrices, which in this case is 3.

  2. We create a Counter to keep track of the translation vectors - delta_i and delta_j, which denote the row and column differences, respectively.

  3. Then, we iterate over each cell in img1:

    • For cell (0,0) in img1, which contains a 1, we check every cell in img2. Only cells (1,1) and (2,2) contain a 1 in img2.
  4. For each 1 in img2, we calculate the translation vectors necessary to overlap this 1 with the 1 at (0,0) in img1:

    • To overlap (0,0) from img1 onto (1,1) in img2, we calculate the translation vector as (1 - 0, 1 - 0) which is (1, 1).
    • To overlap (0,0) from img1 onto (2,2) in img2, the translation vector is (2 - 0, 2 - 0) which is (2, 2).
  5. We add and/or increment the count of these vectors in our Counter.

  6. We repeat steps 3-5 for the other 1 at position (1,1) in img1:

    • There is one 1 at (1,1) in img1 which corresponds directly to the 1 at (1,1) in img2. The translation vector in this case is (1 - 1, 1 - 1) which is (0, 0).
  7. We increment the count of this vector in our Counter. Now our Counter has counted translation vectors with counts as follows:

    • (1, 1): 1 count
    • (2, 2): 1 count
    • (0, 0): 1 count
  8. Finally, we scan through our Counter to determine the maximum overlap, which is 1 in this case since each translation only overlaps one 1 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 in n^2 iterations, where n is the length of the matrix side.
  • The two inner loops iterate over each cell of the img2 matrix, also resulting in n^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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following uses divide and conquer strategy?


Recommended Readings

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.