# 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:

| Value | Meaning |
|---|---|
| `0` | Empty pixel |
| `1` | Filled pixel |

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

| Item | Meaning |
|---|---|
| Input | Two binary matrices `img1` and `img2` |
| Output | Maximum number of overlapping `1` cells |
| Translation | Shift left, right, up, or down |
| Not allowed | Rotation |
| Matrix size | Both matrices are `n x n` |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
3
```

Example 2:

```python
img1 = [[1]]
img2 = [[1]]
```

The two single cells already overlap.

So the answer is:

```python
1
```

Example 3:

```python
img1 = [[0]]
img2 = [[0]]
```

There are no `1` cells.

So the answer is:

```python
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:

```python
-(n - 1) to n - 1
```

because shifting farther than that makes the images completely separate.

This gives a correct solution.

```python
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:

```python
(2n - 1) * (2n - 1)
```

possible shifts.

For each shift, we may scan all:

```python
n * n
```

cells.

So the time complexity is:

```python
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:

```python
(r1, c1)
```

and a `1` cell in `img2` is at:

```python
(r2, c2)
```

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

```python
(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:

```python
shift_count[(dr, dc)] += 1
```

where:

```python
dr = r2 - r1
dc = c2 - c1
```

## Walkthrough

Use:

```python
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:

```python
(0, 0), (0, 1), (1, 1), (2, 1)
```

The `1` positions in `img2` are:

```python
(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:

```python
(1 - 0, 1 - 0) = (1, 1)
```

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

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

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

```python
(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:

```python
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:

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2 + a * b)` | Scan both matrices, then compare pairs of `1` cells |
| Space | `O(a + b + a * b)` | Store `1` positions and shift counts |

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

Then the worst-case time is:

```python
O(n^4)
```

The advantage is that sparse images are much faster.

## Implementation

```python
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:

```python
ones1 = []
ones2 = []
```

During one scan, we fill both lists:

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

Then we count translation vectors:

```python
shift_count = Counter()
```

For every pair of `1` cells:

```python
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:

```python
shift_count[(dr, dc)] += 1
```

The largest count is the largest overlap:

```python
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

```python
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:

| Test | Why |
|---|---|
| Standard example | Confirms translation can create overlap `3` |
| Single `1` cell | Confirms exact overlap |
| Single `0` cell | Confirms no overlap |
| Diagonal shift | Confirms shifting works |
| Identical images | Confirms no shift can be best |