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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Image Overlap

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem involves translating one binary matrix over another and counting overlapping 1s.
  • We need to consider all possible translations of one matrix over the other, both horizontally and vertically.
  • The maximum overlap can be found by checking for each possible translation and counting the overlapping 1s.

Space and Time Complexity

Time Complexity: O(n^4)
Space Complexity: O(1)

Solution

To solve the problem, we can use a brute-force approach by translating img1 over img2 in all possible ways. We will slide img1 across img2 in both horizontal and vertical directions. For each translation, we will calculate the overlap by counting the number of positions where both img1 and img2 have a 1. The overlap is calculated by checking all positions that fall within the matrix borders after translation. We will keep track of the maximum overlap found during these translations.

Code Solutions

def largestOverlap(img1, img2):
    n = len(img1)
    max_overlap = 0
    
    # Helper function to count overlap for a given translation
    def countOverlap(x_offset, y_offset):
        count = 0
        for i in range(n):
            for j in range(n):
                if (0 <= i + x_offset < n) and (0 <= j + y_offset < n):
                    count += img1[i][j] * img2[i + x_offset][j + y_offset]
        return count

    # Try all possible translations
    for x in range(-n + 1, n):
        for y in range(-n + 1, n):
            max_overlap = max(max_overlap, countOverlap(x, y))

    return max_overlap
← Back to All Questions