304. Image Overlap

A translation is fully described by a single vector. Every 1 in img1 paired with a 1 in img2 votes for one translation vector; the vector with the most votes is the best overlap.

Key insight

A translation slides every 1-bit of img1 by the same offset (dr, dc). After that slide, a 1 at position (r1, c1) in img1 lands on (r1 + dr, c1 + dc). It contributes to the overlap only if img2 also has a 1 there.

So for a fixed offset (dr, dc), the overlap equals the number of 1-cells in img1 that map onto a 1-cell in img2. Instead of trying every offset and re-scanning, flip the question around: each pair (one 1 from img1, one 1 from img2) uniquely determines the offset that would make them coincide — namely (r2 - r1, c2 - c1). Count how many pairs produce each offset; the largest count is the answer.

Algorithm

1. Collect the coordinates of all 1-cells in img1 (ones1) and in img2 (ones2).
2. For every (r1, c1) in ones1 and every (r2, c2) in ones2, compute the offset (r2 - r1, c2 - c1) and increment a counter for that offset in a hash map.
3. The maximum counter value is the largest overlap. If either image has no 1s, the answer is 0.

Worked example

img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]].

• ones1 = [(0,0),(0,1),(1,1),(2,1)]
• ones2 = [(1,1),(1,2),(2,2)]

Consider the offset (dr, dc) = (1, 1) (slide img1 right 1 and down 1):

• (0,0) -> (1,1) — img2 has a 1 there ✓
• (0,1) -> (1,2) — img2 has a 1 there ✓
• (1,1) -> (2,2) — img2 has a 1 there ✓
• (2,1) -> (3,2) — falls off the board ✗

The offset (1,1) is voted for by three pairs, and no offset gets more votes, so the answer is 3.

Complexity

Let k1 and k2 be the number of 1-cells in each image (k <= n^2).

• Time: O(k1 * k2), at most O(n^4). For n <= 30 this is fast.
• Space: O(k1 * k2) for the offset counter in the worst case.

class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        List<int[]> ones1 = new ArrayList<>();
        List<int[]> ones2 = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (img1[r][c] == 1) ones1.add(new int[]{r, c});
                if (img2[r][c] == 1) ones2.add(new int[]{r, c});
            }
        }

        Map<Integer, Integer> counts = new HashMap<>();
        int best = 0;
        for (int[] a : ones1) {
            for (int[] b : ones2) {
                // Encode the offset (dr, dc); dr, dc range over [-(n-1), n-1].
                int key = (b[0] - a[0] + n) * (2 * n + 1) + (b[1] - a[1] + n);
                int v = counts.merge(key, 1, Integer::sum);
                best = Math.max(best, v);
            }
        }
        return best;
    }
}