# Image Overlap
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/image-overlap)
Canonical: https://scaleengineer.com/dsa/problems/image-overlap
**Data structures:** Array, Matrix
---
## Problem
You are given two images, `img1` and `img2`, represented as binary, square matrices of size `n x n`. A binary matrix has only `0`s and `1`s 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_.

**Example 1:**

![](https://assets.glich.co/dsa/image-overlap/image0.jpg) 

**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.
![](https://assets.glich.co/dsa/image-overlap/image1.jpg)
The number of positions that have a 1 in both images is 3 (shown in red).
![](https://assets.glich.co/dsa/image-overlap/image2.jpg)

**Example 2:**

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

**Example 3:**

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

**Constraints:**

* `n == img1.length == img1[i].length`
* `n == img2.length == img2[i].length`
* `1 <= n <= 30`
* `img1[i][j]` is either `0` or `1`.
* `img2[i][j]` is either `0` or `1`.

# Approaches
## Brute-Force Shift and Count
This is the most straightforward approach. We can simulate every possible translation of `img1` and, for each translation, count the number of overlapping `1`s with `img2`. The maximum count found among all translations is the answer.
**Time:** O(n^4). There are `O(n^2)` possible translations (`(2n-1) * (2n-1)`). For each translation, we iterate through the `n x n` grid to count the overlap, which takes `O(n^2)` time. · **Space:** O(1). We only use a few variables to store the shifts and counts, so the space is constant.
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Very inefficient, especially for larger `n`.; Performs many redundant checks on cells that contain `0`s and cannot contribute to the overlap.
### Explanation
We consider all possible relative translations between the two images. A translation can be represented by a vector `(dx, dy)`, where `dx` is the horizontal shift and `dy` is the vertical shift.

To ensure we cover all possibilities of overlap, the shifts `dx` and `dy` must range from `-(n-1)` to `n-1`, where `n` is the dimension of the matrix. This gives `(2n-1) * (2n-1)` possible translations.

For each translation `(dx, dy)`:
- We initialize a counter for the current overlap to zero.
- We iterate through every cell `(r, c)` of `img1`.
- We calculate the corresponding cell's coordinates `(r + dy, c + dx)` in `img2`'s grid.
- If this translated coordinate is within the bounds of `img2` (i.e., `0 <= r + dy < n` and `0 <= c + dx < n`), and both `img1[r][c]` and `img2[r + dy][c + dx]` are `1`, we increment the overlap counter.

We keep track of the maximum overlap found across all translations and return it.

```java
class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        int maxOverlap = 0;

        for (int dy = -n + 1; dy < n; dy++) {
            for (int dx = -n + 1; dx < n; dx++) {
                maxOverlap = Math.max(maxOverlap, countOverlap(img1, img2, dx, dy));
            }
        }
        return maxOverlap;
    }

    private int countOverlap(int[][] img1, int[][] img2, int dx, int dy) {
        int n = img1.length;
        int count = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int tr = r + dy;
                int tc = c + dx;

                if (tr >= 0 && tr < n && tc >= 0 && tc < n) {
                    if (img1[r][c] == 1 && img2[tr][tc] == 1) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `maxOverlap = 0`.
- Get the dimension `n` of the images.
- Loop for vertical shift `dy` from `-(n-1)` to `n-1`.
- Loop for horizontal shift `dx` from `-(n-1)` to `n-1`.
    - Initialize `currentOverlap = 0`.
    - Loop for row `r` from `0` to `n-1`.
    - Loop for column `c` from `0` to `n-1`.
        - Calculate the translated coordinates in `img2`: `tr = r + dy` and `tc = c + dx`.
        - Check if `(tr, tc)` is within the bounds of the `n x n` grid.
        - If it is, and both `img1[r][c]` and `img2[tr][tc]` are `1`, increment `currentOverlap`.
    - Update `maxOverlap = max(maxOverlap, currentOverlap)`.
- Return `maxOverlap`.

## Optimized Search using Coordinate Lists and Hashing
The brute-force approach is inefficient because it iterates over all `n x n` cells for every shift, regardless of whether they contain `1`s or `0`s. We can optimize this by only considering the cells that contain `1`s, as these are the only ones that can contribute to the overlap.
**Time:** O(n^2 + N1 * N2), where `N1` and `N2` are the number of `1`s in `img1` and `img2` respectively. The `O(n^2)` part is for finding the coordinates of the `1`s. The `O(N1 * N2)` part is for iterating through all pairs of `1`s. In the worst case, `N1` and `N2` can be `O(n^2)`, leading to `O(n^4)` complexity. · **Space:** O(N1 + N2). We need space to store the lists of coordinates and the hash map. `N1` and `N2` are the number of `1`s in each image. The map can store up to `min(N1 * N2, (2n-1)^2)` distinct vectors. In the worst case, this is `O(n^2)`.
**Pros:** Much more efficient than brute-force for sparse matrices (matrices with few `1`s).; Avoids unnecessary computations involving zero-valued cells.
**Cons:** The worst-case time complexity is still `O(n^4)` if the matrices are dense (full of `1`s).; The space complexity can be high in the worst case, up to `O(n^2)`.
### Explanation
The core idea is to reframe the problem. Instead of trying every possible shift, we consider pairs of `1`s, one from `img1` and one from `img2`, and determine the translation vector that would make them overlap.

First, we iterate through both `img1` and `img2` to create lists of coordinates for all the `1`s. Let's call these `ones1` and `ones2`.

Then, we iterate through every pair of points `(p1, p2)` where `p1` is from `ones1` and `p2` is from `ones2`.
For each pair `p1 = (r1, c1)` and `p2 = (r2, c2)`, we calculate the translation vector `(dr, dc) = (r2 - r1, c2 - c1)` that would align `p1` with `p2`.

We use a hash map to store the frequency of each translation vector. The key can be a string representation of the vector (e.g., `"dr,dc"`) and the value is its count.

After counting the occurrences of all possible translation vectors, the maximum value in the hash map represents the largest number of `1`s that can be aligned simultaneously, which is the largest overlap. If either image has no `1`s, the overlap is `0`.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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});
                }
            }
        }

        if (ones1.isEmpty() || ones2.isEmpty()) {
            return 0;
        }

        Map<String, Integer> vectorCounts = new HashMap<>();
        int maxOverlap = 0;

        for (int[] p1 : ones1) {
            for (int[] p2 : ones2) {
                String vector = (p2[0] - p1[0]) + "," + (p2[1] - p1[1]);
                vectorCounts.put(vector, vectorCounts.getOrDefault(vector, 0) + 1);
                maxOverlap = Math.max(maxOverlap, vectorCounts.get(vector));
            }
        }
        
        return maxOverlap;
    }
}
```
### Algorithm
- Create a list `ones1` to store coordinates of `1`s in `img1`.
- Create a list `ones2` to store coordinates of `1`s in `img2`.
- Populate `ones1` and `ones2` by iterating through the input matrices.
- If either list is empty, return `0`.
- Initialize a hash map `vectorCounts` to store `(translation_vector -> count)`.
- Initialize `maxOverlap = 0`.
- For each point `p1 = (r1, c1)` in `ones1`:
    - For each point `p2 = (r2, c2)` in `ones2`:
        - Calculate the vector `v = (r2 - r1, c2 - c1)`.
        - Increment the count for `v` in `vectorCounts`.
        - Update `maxOverlap` with the new count for `v`.
- Return `maxOverlap`.

## Efficient Overlap Calculation using Bit Manipulation
Given the constraint `n <= 30`, we can represent each row of the `n x n` matrix as a single 32-bit integer. This allows us to use fast bitwise operations to calculate the overlap for each row, leading to a more efficient solution with a better worst-case time complexity.
**Time:** O(n^3). The initial data transformation takes `O(n^2)`. The main part consists of two loops for shifts `(dx, dy)` giving `O(n^2)` translations, and for each, an inner loop over `n` rows. The operations inside the innermost loop are constant time. · **Space:** O(n). We use two arrays of size `n` to store the integer representations of the rows.
**Pros:** Significantly faster worst-case performance than the other approaches.; Cleverly uses hardware-level bit operations for efficient computation.
**Cons:** The logic can be slightly more complex to grasp than the straightforward brute-force method.; It's only applicable because `n` is small enough (`n <= 30`) to fit a row into a standard integer type (32-bit).
### Explanation
First, we transform the input matrices `img1` and `img2` into arrays of integers. For each matrix, we create an array of size `n`, where the `i`-th element stores the integer representation of the `i`-th row. This is done by iterating through the row and using bit shifting. For example, `row_val = (row_val << 1) | bit`.

After this preprocessing, we iterate through all possible translations `(dx, dy)`, similar to the brute-force approach.

For a given translation `(dx, dy)`, we calculate the total overlap. We iterate through the rows of `img2` (from `r2 = 0` to `n-1`). The corresponding row in `img1` is `r1 = r2 - dy`.

If `r1` is a valid row index for `img1`, we take the integer representation of that row, `b1[r1]`. We then apply the horizontal shift `dx` to this integer using bitwise shift operators (`>>` for right shift, `<<` for left shift).

The overlap for this pair of rows is the number of common `1`s after shifting. This can be calculated by performing a bitwise AND between the shifted `img1` row and the `img2` row (`shifted_b1_row & b2[r2]`) and then counting the number of set bits in the result. Java's `Integer.bitCount()` is perfect for this.

We sum these row-wise overlaps to get the total overlap for the translation `(dx, dy)` and return the maximum found.

```java
class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        int[] b1 = new int[n];
        int[] b2 = new int[n];

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                b1[r] = (b1[r] << 1) | img1[r][c];
                b2[r] = (b2[r] << 1) | img2[r][c];
            }
        }

        int maxOverlap = 0;
        for (int dy = -n + 1; dy < n; dy++) {
            for (int dx = -n + 1; dx < n; dx++) {
                int currentOverlap = 0;
                for (int r2 = 0; r2 < n; r2++) {
                    int r1 = r2 - dy;
                    if (r1 >= 0 && r1 < n) {
                        int shifted_b1_row;
                        if (dx >= 0) {
                            shifted_b1_row = b1[r1] >> dx;
                        } else {
                            shifted_b1_row = b1[r1] << (-dx);
                        }
                        currentOverlap += Integer.bitCount(shifted_b1_row & b2[r2]);
                    }
                }
                maxOverlap = Math.max(maxOverlap, currentOverlap);
            }
        }
        return maxOverlap;
    }
}
```
### Algorithm
- Get the dimension `n`.
- Create two integer arrays, `b1` and `b2`, of size `n`.
- For each row `r` from `0` to `n-1`:
    - Convert `img1[r]` and `img2[r]` to integers and store them in `b1[r]` and `b2[r]`.
- Initialize `maxOverlap = 0`.
- Loop for `dy` from `-(n-1)` to `n-1`.
- Loop for `dx` from `-(n-1)` to `n-1`.
    - Initialize `currentOverlap = 0`.
    - Loop for row `r2` from `0` to `n-1`.
        - Calculate the corresponding `img1` row index `r1 = r2 - dy`.
        - If `r1` is valid (i.e., `0 <= r1 < n`):
            - Get the integer for `img1`'s row: `row1_val = b1[r1]`.
            - Apply horizontal shift `dx`: `shifted_row1 = (dx >= 0) ? (row1_val >> dx) : (row1_val << -dx)`.
            - Get the integer for `img2`'s row: `row2_val = b2[r2]`.
            - Calculate overlap for this row pair: `Integer.bitCount(shifted_row1 & row2_val)`.
            - Add this to `currentOverlap`.
    - Update `maxOverlap = max(maxOverlap, currentOverlap)`.
- Return `maxOverlap`.

# Solutions
### Java

```java
class Solution {
public
  int largestOverlap(int[][] img1, int[][] img2) {
    int n = img1.length;
    Map<List<Integer>, Integer> cnt = new HashMap<>();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (img1[i][j] == 1) {
          for (int h = 0; h < n; ++h) {
            for (int k = 0; k < n; ++k) {
              if (img2[h][k] == 1) {
                List<Integer> t = List.of(i - h, j - k);
                ans = Math.max(ans, cnt.merge(t, 1, Integer : : sum));
              }
            }
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestOverlap(vector<vector<int>> &img1, vector<vector<int>> &img2) {
    int n = img1.size();
    map<pair<int, int>, int> cnt;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (img1[i][j]) {
          for (int h = 0; h < n; ++h) {
            for (int k = 0; k < n; ++k) {
              if (img2[h][k]) {
                ans = max(ans, ++cnt[{i - h, j - k}]);
              }
            }
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int: n = len(img1) cnt = Counter() for i in range(n): for j in range(n): if img1[i][j]: for h in range(n): for k in range(n): if img2[h][k]: cnt[(i - h, j - k)] += 1 return max(cnt . values()) if cnt else 0

```