algoadvance

You are given two binary matrices img1 and img2 of size n x n. The overlap of one binary matrix on another is defined as the number of positions that have a 1 in both matrices.

In other words, we translate one matrix over the other, and the overlap is the count of positions where both matrices have a 1.

Your task is to find the largest possible overlap of these two matrices.

Example:

Input: img1 = [[1,1,0],
               [0,1,0],
               [0,1,0]], 
       img2 = [[0,0,0],
               [0,1,1],
               [0,0,1]]
Output: 3

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.

Clarifying Questions

1. Should we consider shifting in all four directions (up, down, left, right)?
   • Yes, you should consider all possible shifts of one matrix over another.
2. Do we count overlap for positions that go out of bounds of the matrices?
   • No, only consider valid positions that remain within the bounds of the matrices.
3. Should matrices be flexible to rotate or flip over?
   • No, only translations (shifts) are allowed.

Strategy

1. Brute-force Approach:
   • For all possible translations (shifts) of img1 over img2 in vertical and horizontal directions:
     • Calculate the overlap for each translation.
     • Keep track of the maximum overlap encountered.

When img1 shifts over img2, both matrices should be compared within the boundaries (i.e., do not consider regions that go out of bounds).

Code

Here’s the brute-force approach to solving this problem:

def largestOverlap(img1, img2):
    def shift_and_count(x_shift, y_shift, M, R):
        n = len(M)
        count = 0
        for r in range(n):
            for c in range(n):
                if 0 <= r + y_shift < n and 0 <= c + x_shift < n:
                    if M[r][c] == 1 and R[r + y_shift][c + x_shift] == 1:
                        count += 1
        return count
    
    n = len(img1)
    max_overlaps = 0
    
    for y_shift in range(-n + 1, n):
        for x_shift in range(-n + 1, n):
            max_overlaps = max(max_overlaps, shift_and_count(x_shift, y_shift, img1, img2))
            max_overlaps = max(max_overlaps, shift_and_count(x_shift, y_shift, img2, img1))
            
    return max_overlaps

Time Complexity

• There are 2 * (2n-1) * (2n-1) shifts to consider (since we check both img1 over img2 and img2 over img1).
• For each shift, we need to check the entire matrix, which requires an O(n^2) operation.
• Thus, the time complexity is O(n^4).

This brute-force approach is efficient given the constraint that 1 <= n <= 30.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?