835. Image Overlap

Array
Hash Table
Matrix

TIME

O(k1 * k2)

SPACE

O(n^2)

Intuition

A translation is fully described by one offset vector (dr, dc). Under that translation, a 1 at (r, c) in img1 lands on (r + dr, c + dc), and it contributes to the overlap exactly when img2 has a 1 there.

Flip the question around. Instead of picking a translation and counting overlaps, look at every pair of a 1 in img1 and a 1 in img2. That pair overlaps under exactly one translation, the vector that carries the first onto the second: (r2 - r1, c2 - c1). So if each pair casts a vote for its vector, the number of votes a vector receives is precisely the overlap that translation produces. The answer is the largest vote count.

This also makes the border rule automatic. A 1 that would be shifted off the grid never aligns with any 1 in img2, so it simply never appears in a pair.

Approach

Collect the coordinates of every 1 in img1 and every 1 in img2.
For every pair (p1, p2), increment a counter keyed by the vector (p2.r - p1.r, p2.c - p1.c).
Return the maximum counter value, or 0 if either image has no 1s.

Encoding the vector as a single integer (offset both components by n so they are non-negative) allows a flat array instead of a hash map in Java.

Complexity

Time: O(k1 * k2), where k1, k2 are the counts of 1s (each at most n^2 = 900), so about 8 * 10^5 pair checks at worst
Space: O(n^2), at most (2n - 1)^2 distinct vectors

Edge Cases

Either image entirely 0 → no pairs → 0 (Example 3)
Both images [[1]] → the zero vector gets one vote → 1 (Example 2)
The zero translation (no shift) is just another vector and needs no special handling
Identical images → the zero vector wins with a count equal to the number of 1s
Vector components range over [-(n-1), n-1], so an array index needs an offset of n - 1 or larger

Code

from typing import List
from collections import defaultdict


class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        """
        835. Image Overlap
        Time: O(k1 * k2)
        Space: O(n^2)
        """
        n = len(img1)
        ones1 = [(r, c) for r in range(n) for c in range(n) if img1[r][c]]
        ones2 = [(r, c) for r in range(n) for c in range(n) if img2[r][c]]

        # each (1, 1) pair votes for the one translation that aligns them
        votes = defaultdict(int)
        for r1, c1 in ones1:
            for r2, c2 in ones2:
                votes[(r2 - r1, c2 - c1)] += 1

        return max(votes.values(), default=0)

import java.util.ArrayList;
import java.util.List;

/**
 * 835. Image Overlap
 * Time: O(k1 * k2)
 * Space: O(n^2)
 */
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});
                }
            }
        }

        // vector components lie in [-(n-1), n-1]; shift by n-1 to index a flat array
        int span = 2 * n - 1;
        int[] votes = new int[span * span];
        int best = 0;

        // each (1, 1) pair votes for the one translation that aligns them
        for (int[] p1 : ones1) {
            for (int[] p2 : ones2) {
                int dr = p2[0] - p1[0] + n - 1;
                int dc = p2[1] - p1[1] + n - 1;
                int key = dr * span + dc;
                votes[key]++;
                if (votes[key] > best) {
                    best = votes[key];
                }
            }
        }

        return best;
    }
}