Problem

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.

Examples

Example 1:

$$ img1 = \begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix} \text{ | } img2 = \begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} $$

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.

$$ img1 = \begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix} \implies \begin{matrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix} \implies \begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} $$

The number of positions that have a 1 in both images is 3 (shown in red).

$$ img1 = \begin{matrix} 0 & 0 & 0 \\ 0 & \colorbox{red} 1 & \colorbox{red} 1 \\ 0 & 0 & \colorbox{red} 1 \end{matrix} \text{ | } img2 = \begin{matrix} 0 & 0 & 0 \\ 0 & \colorbox{red} 1 & \colorbox{red} 1 \\ 0 & 0 & \colorbox{red} 1 \end{matrix} $$

Example 2:

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

Example 3:

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

Solution

Method 1 - Brute Force Translation and Overlap Calculation

Here is the approach:

  1. Brute Force Translation:
    • For each possible translation (x_shift, y_shift), slide img1 over img2 and compute the number of overlapping 1 bits.
    • The translation can range from -n + 1 to n - 1 for both x and y directions, ensuring we cover all possible relative positions of the two images.
  2. Computing Overlaps:
    • For each combination of x_shift and y_shift, translate img1 and count the number of overlapping 1s with img2.
    • Keep track of the maximum overlap observed.

Code

Java
public class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        int maxOverlap = 0;
        
        // Brute force over all possible translations
        for (int x_shift = -n + 1; x_shift < n; x_shift++) {
            for (int y_shift = -n + 1; y_shift < n; y_shift++) {
                maxOverlap = Math.max(maxOverlap, calculateOverlap(img1, img2, x_shift, y_shift));
                maxOverlap = Math.max(maxOverlap, calculateOverlap(img2, img1, x_shift, y_shift));
            }
        }
        
        return maxOverlap;
    }

    private int calculateOverlap(int[][] img1, int[][] img2, int x_shift, int y_shift) {
        int n = img1.length;
        int overlap = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int img1_i = i + x_shift;
                int img1_j = j + y_shift;
                if (img1_i >= 0 && img1_i < n && img1_j >= 0 && img1_j < n) {
                    if (img1[i][j] == 1 && img2[img1_i][img1_j] == 1) {
                        overlap++;
                    }
                }
            }
        }
        
        return overlap;
    }
}
Python
class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        max_overlap = 0

        def calculate_overlap(img1: List[List[int]], img2: List[List[int]], x_shift: int, y_shift: int) -> int:
            overlap = 0
            for i in range(n):
                for j in range(n):
                    img1_i = i + x_shift
                    img1_j = j + y_shift
                    if 0 <= img1_i < n and 0 <= img1_j < n:
                        if img1[i][j] == 1 and img2[img1_i][img1_j] == 1:
                            overlap += 1
            return overlap

        for x_shift in range(-n + 1, n):
            for y_shift in range(-n + 1, n):
                max_overlap = max(max_overlap, calculate_overlap(img1, img2, x_shift, y_shift))
                max_overlap = max(max_overlap, calculate_overlap(img2, img1, x_shift, y_shift))

        return max_overlap

Complexity

  • Time: O(n^4) because the algorithm checks each possible translation (n^2 possibilities) and for each translation, it checks n^2 elements.
  • Space: O(1), as we are using a fixed amount of extra space for tracking the maximum overlap and the current overlap count.