LeetCode 835: Image Overlap

Problem Restatement

We are given two binary square matrices img1 and img2, both of size n x n.

Each cell is either:

We may translate one image by sliding it left, right, up, or down by any number of units. Translation does not include rotation.

After translation, some 1 cells may move outside the matrix border and disappear.

The overlap is the number of positions where both images have 1.

Return the largest possible overlap.

Input and Output

Function shape:

class Solution:
    def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
        ...

Examples

Example 1:

img1 = [
    [1, 1, 0],
    [0, 1, 0],
    [0, 1, 0],
]

img2 = [
    [0, 0, 0],
    [0, 1, 1],
    [0, 0, 1],
]

If we translate img1 right by 1 and down by 1, then three 1 cells overlap.

So the answer is:

3

Example 2:

img1 = [[1]]
img2 = [[1]]

The two single cells already overlap.

So the answer is:

1

Example 3:

img1 = [[0]]
img2 = [[0]]

There are no 1 cells.

So the answer is:

0

First Thought: Try Every Shift

A direct approach is to try every possible row shift and column shift.

For each shift, count how many 1 cells overlap.

The row shift and column shift can range from:

-(n - 1) to n - 1

because shifting farther than that makes the images completely separate.

This gives a correct solution.

class Solution:
    def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
        n = len(img1)
        answer = 0

        for dr in range(-(n - 1), n):
            for dc in range(-(n - 1), n):
                overlap = 0

                for r in range(n):
                    for c in range(n):
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            if img1[r][c] == 1 and img2[nr][nc] == 1:
                                overlap += 1

                answer = max(answer, overlap)

        return answer

Problem With Trying Every Shift

There are about:

(2n - 1) * (2n - 1)

possible shifts.

For each shift, we may scan all:

n * n

cells.

So the time complexity is:

O(n^4)

For this problem, that can pass because n is small, but there is a cleaner idea.

Key Insight

Only 1 cells matter.

Suppose a 1 cell in img1 is at:

(r1, c1)

and a 1 cell in img2 is at:

(r2, c2)

To make these two cells overlap, we need to shift one image by:

(r2 - r1, c2 - c1)

Every pair of 1 cells gives one translation vector.

If the same translation vector appears many times, that means many 1 cells can overlap under the same shift.

So the answer is the maximum frequency of any translation vector.

Algorithm

1. Collect all positions of 1 in img1.
2. Collect all positions of 1 in img2.
3. For every pair (p1, p2), compute the translation vector that moves p1 onto p2.
4. Count how many times each vector appears.
5. Return the largest count.

Use a hash map:

shift_count[(dr, dc)] += 1

where:

dr = r2 - r1
dc = c2 - c1

Walkthrough

Use:

img1 = [
    [1, 1, 0],
    [0, 1, 0],
    [0, 1, 0],
]

img2 = [
    [0, 0, 0],
    [0, 1, 1],
    [0, 0, 1],
]

The 1 positions in img1 are:

(0, 0), (0, 1), (1, 1), (2, 1)

The 1 positions in img2 are:

(1, 1), (1, 2), (2, 2)

Now compare every pair.

For example, to move (0, 0) in img1 onto (1, 1) in img2, the shift is:

(1 - 0, 1 - 0) = (1, 1)

To move (0, 1) in img1 onto (1, 2) in img2, the shift is also:

(1 - 0, 2 - 1) = (1, 1)

To move (1, 1) in img1 onto (2, 2) in img2, the shift is also:

(2 - 1, 2 - 1) = (1, 1)

The shift (1, 1) appears 3 times.

That means shifting img1 down by 1 and right by 1 produces 3 overlapping 1 cells.

So the answer is:

3

Correctness

For any pair of 1 cells, one from img1 and one from img2, there is exactly one translation vector that makes those two cells occupy the same position.

If a translation vector appears k times among all pairs, then there are k pairs of 1 cells that become aligned under that translation.

Because translation moves every cell by the same row and column offset, all pairs counted under the same vector overlap simultaneously.

Therefore, the number of overlapping 1 cells produced by a translation is exactly the frequency of its translation vector.

The algorithm counts the frequency of every translation vector generated by pairs of 1 cells and returns the maximum frequency. Thus it returns the largest possible overlap.

If either image has no 1 cells, there are no pairs, so no overlap is possible and the answer is 0.

Complexity

Let:

a = number of 1 cells in img1
b = number of 1 cells in img2

In the worst case, both matrices are full of 1s, so a = b = n^2.

Then the worst-case time is:

O(n^4)

The advantage is that sparse images are much faster.

Implementation

from collections import Counter

class Solution:
    def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
        n = len(img1)

        ones1 = []
        ones2 = []

        for r in range(n):
            for c in range(n):
                if img1[r][c] == 1:
                    ones1.append((r, c))
                if img2[r][c] == 1:
                    ones2.append((r, c))

        shift_count = Counter()

        for r1, c1 in ones1:
            for r2, c2 in ones2:
                dr = r2 - r1
                dc = c2 - c1
                shift_count[(dr, dc)] += 1

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

Code Explanation

We first collect the coordinates of all 1 cells:

ones1 = []
ones2 = []

During one scan, we fill both lists:

if img1[r][c] == 1:
    ones1.append((r, c))
if img2[r][c] == 1:
    ones2.append((r, c))

Then we count translation vectors:

shift_count = Counter()

For every pair of 1 cells:

dr = r2 - r1
dc = c2 - c1

This is the shift that moves the img1 cell onto the img2 cell.

We increase that shift’s count:

shift_count[(dr, dc)] += 1

The largest count is the largest overlap:

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

The default=0 handles the case where there are no 1 cells in at least one image.

Testing

def run_tests():
    s = Solution()

    assert s.largestOverlap(
        [
            [1, 1, 0],
            [0, 1, 0],
            [0, 1, 0],
        ],
        [
            [0, 0, 0],
            [0, 1, 1],
            [0, 0, 1],
        ],
    ) == 3

    assert s.largestOverlap([[1]], [[1]]) == 1
    assert s.largestOverlap([[0]], [[0]]) == 0

    assert s.largestOverlap(
        [
            [1, 0],
            [0, 0],
        ],
        [
            [0, 0],
            [0, 1],
        ],
    ) == 1

    assert s.largestOverlap(
        [
            [1, 0],
            [0, 1],
        ],
        [
            [1, 0],
            [0, 1],
        ],
    ) == 2

    print("all tests passed")

run_tests()

Test meaning: