We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Image Overlap

Number: 864

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two n x n binary matrices representing images, the goal is to translate one image (i.e. slide it left/right/up/down) to maximize the number of overlapping 1's when it is superimposed on the other image. Note that rotations are not allowed and any 1’s moved outside the border get erased.

Key Insights

  • You only need to consider the positions of 1’s in each matrix.
  • The overlap count for a given translation can be computed by comparing the relative differences between the positions of 1’s in the two images.
  • Using a hash map (or dictionary) to count how many times each translation vector appears lets you compute the maximum overlap efficiently.
  • The translation operation is equivalent to shifting the positions, so the best possible translation is the one that aligns the most pairs of 1’s.

Space and Time Complexity

Time Complexity: O(n^4) in the worst-case when using a nested iteration over positions for both matrices, though the average situation is typically better since not all cells are 1. Space Complexity: O(n^2) for storing the positions of 1’s and the counts for translation vectors.

Solution

The solution involves the following steps:

  1. Traverse both images to record the coordinates of all 1’s.
  2. For every pair of 1’s (one from the first image, one from the second), compute the translation vector (offset) that aligns them.
  3. Use a hash map to count how many times each offset appears.
  4. The maximum count recorded in the hash map is the largest overlap achievable by any translation. This approach avoids simulating every possible slide over the matrix and focuses only on relative alignments of 1’s.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed line-by-line comments.

def largestOverlap(img1, img2):
    # Get the dimension of the square images
    n = len(img1)
    
    # Gather positions (coordinates) where there is a 1 in img1 and img2
    ones_img1 = []
    ones_img2 = []
    for i in range(n):
        for j in range(n):
            if img1[i][j] == 1:
                ones_img1.append((i, j))
            if img2[i][j] == 1:
                ones_img2.append((i, j))
                
    # Dictionary to count translation shifts that align 1's of img1 with img2
    translation_count = {}
    max_overlap = 0
    
    # Iterate over every pair of 1's from both images
    for (x1, y1) in ones_img1:
        for (x2, y2) in ones_img2:
            # Calculate the translation vector needed to align img1's 1 with img2's 1
            delta = (x2 - x1, y2 - y1)
            # Update the count for this translation vector
            translation_count[delta] = translation_count.get(delta, 0) + 1
            # Update max_overlap if we find a higher count
            max_overlap = max(max_overlap, translation_count[delta])
    
    return max_overlap

# Example usage:
img1 = [[1,1,0],[0,1,0],[0,1,0]]
img2 = [[0,0,0],[0,1,1],[0,0,1]]
print(largestOverlap(img1, img2))  # Expected output: 3
← Back to All Questions