Image Overlap LeetCode Solution

Difficulty Level Medium
Frequently asked in GoogleViews 2089

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 0s and 1s 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.

Image Overlap LeetCode Solution

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

Reference: https://en.wikipedia.org/wiki/Logical_matrix

Translate »