{x}
blog image

Image Overlap

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].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.

Solution Explanation: Image Overlap

This problem asks to find the maximum overlap between two binary square images after translating one image over the other. The solution involves efficiently finding the best translation that maximizes the overlapping 1s.

Approach: Brute Force with Optimization

A straightforward approach is to consider all possible translations of img1 over img2. For each translation, we count the number of overlapping 1s. The translation that yields the maximum overlap is the solution.

While a completely brute-force approach would check every possible x and y offset, we can optimize it. We only need to iterate through the coordinates where img1 has a 1. For each such coordinate, we can check all possible coordinates of img2 that contain a 1 and compute the offset. Using a hash map (dictionary in Python) to store these offsets and their counts allows for quick identification of the maximum overlap.

Time Complexity Analysis

The outer loops iterate through each element in img1. For each element which is 1, we then iterate through all elements in img2. Therefore, in the worst case, the time complexity is O(n4), where n is the dimension of the square images. This is because we might have to iterate through each cell of both images multiple times.

Space Complexity Analysis

We use a hash map (cnt) to store the offsets and their counts. In the worst case, the number of unique offsets can be O(n2). Therefore, the space complexity is O(n2).

Code Explanation (Python)

from collections import Counter
 
class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        cnt = Counter()  # Use Counter for efficient counting of offsets
        for i in range(n):
            for j in range(n):
                if img1[i][j]: #Check only if img1[i][j] is 1
                    for h in range(n):
                        for k in range(n):
                            if img2[h][k]: #Check only if img2[h][k] is 1
                                cnt[(i - h, j - k)] += 1 #Store offset and increment count
        return max(cnt.values()) if cnt else 0 #Return maximum count

The Python code utilizes the Counter class from the collections module which is optimized for counting frequencies. This improves efficiency compared to manually tracking counts using a standard dictionary. The if cnt else 0 handles the edge case where no overlaps are found.

Code in Other Languages

The logic remains consistent across different programming languages. The main difference lies in the syntax and data structures used. The Java, C++, Go, and TypeScript code provided in the original response all follow the same algorithmic approach, utilizing hash maps or dictionaries for efficient offset counting. The choice of map implementation varies depending on the language's standard library (HashMap in Java, map in C++, map in Go, Map in TypeScript).