# Image Overlap LeetCode Solution

Difficulty Level Medium

## Problem Statement

Image Overlap LeetCode Solution – 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 an `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.

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

## Explanation

If we do brute force, we have `2N` horizontal possible sliding, `2N` vertical sliding and `N^2` to count overlap area.
We get `O(N^4)` the solution and it may get accepted.
But we waste our time on the case of a sparse matrix.

Assume the index in A and B is [0, N * N -1].

1. Loop on A, if value == 1, save a coordinates `i / N * 100 + i % N` to LA.
2. Loop on B, if value == 1, save a coordinates `i / N * 100 + i % N` to LB.
3. Loop on the combination (i, j) of LA and LB, increase count[i – j] by 1.
If we slide to make A[i] overlap B[j], we can get 1 point.
4. Loop on the count and return max values.

I use a 1 key hashmap. Assume `ab` for row and `cd` for col, I make it `abcd` as coordinate.
For sure, a hashmap with 2 keys will be better for understanding.

Q: Why 100?
100 is big enough and very clear.
For example, If I slide 13 rows and 19 cols, it will be 1319.

Q: Can we replace `i / N * 100 + i % N` by `i`?
No, it’s wrong for a simple test case `[[0,1],[1,1]], [[1,1],[1,0]]`

## Code

### C++ Code for Image Overlap

```class Solution {
public:
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<int> LA, LB;
int N = A.size();
unordered_map<int, int> count;
for (int i = 0; i < N * N; ++i)
if (A[i / N][i % N] == 1)
LA.push_back(i / N * 100 + i % N);
for (int i = 0; i < N * N; ++i)
if (B[i / N][i % N] == 1)
LB.push_back(i / N * 100 + i % N);
for (int i : LA) for (int j : LB) count[i - j]++;
int res = 0;
for (auto it : count) res = max(res, it.second);
return res;
}
};```

### Java Code for Image Overlap

```class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int N = A.length;
List<Integer> LA = new ArrayList<>(),  LB = new ArrayList<>();
HashMap<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < N * N; ++i)
if (A[i / N][i % N] == 1)
LA.add(i / N * 100 + i % N);
for (int i = 0; i < N * N; ++i)
if (B[i / N][i % N] == 1)
LB.add(i / N * 100 + i % N);
for (int i : LA) for (int j : LB)
count.put(i - j, count.getOrDefault(i - j, 0) + 1);
int res = 0;
for (int i : count.values())
res = Math.max(res, i);
return res;
}
}```

### Python Code for Image Overlap

```class Solution:
def largestOverlap(self, A, B):
N = len(A)
LA = [i / N * 100 + i % N for i in xrange(N * N) if A[i / N][i % N]]
LB = [i / N * 100 + i % N for i in xrange(N * N) if B[i / N][i % N]]
c = collections.Counter(i - j for i in LA for j in LB)
return max(c.values() or [0])
```

## Complexity Analysis for Image Overlap LeetCode Solution

### Time Complexity

Assume `A` the number of points in image A, `B` the number of points in image B,
`N = A.length = B.length`.
`O(N^2)` time for preparing,
and `O(AB)` time for the loop.
So overall `O(AB + N^2)` time.

### Space Complexity

Space is `O(A + B)`.

Translate »