Leetcode 835: Image Overlap

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

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.

The number of positions that have a 1 in both images is 3 (shown in red).

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.

Problem Analysis:

If we try to compare all cases, that is comparing img1 from ith row, jth column to img2 from kth row, lth column, the time complexity is O(n⁴).

Assume we have slided the image arbitrarily steps by left, right, up or down. Then we notice that the position of cell between in an image is relatively not changed.

So we assume the cell in img1 ith row, jth column is 1, and cell in img2 kth row, lth column is 1, the diff is i-k row and j-l column. And if another pair of cells is also 1 and diff is the same of i-k row and j-l column, then these pairs of cell can overlap at the same time.

Finally we statistics the numbers of different diffs, the maximum one is the answer.

Solution

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        vector<int> data1, data2;
        unordered_map<int, int> count;
        for (int i = 0; i < img1.size() * img1.size(); ++i) {
            if (img1[i / img1.size()][i % img1.size()] == 1)
                data1.push_back(((i / img1.size()) << 6) + i % img1.size());
        }
        for (int i = 0; i < img1.size() * img1.size(); ++i) {
            if (img2[i / img1.size()][i % img1.size()] == 1)
                data2.push_back(((i / img1.size()) << 6) + i % img1.size());
        }
        for (const auto& item1 : data1) {
            for (const auto& item2 : data2)
                ++count[item1 - item2];
        }
        int res{0};
        for (const auto& item : count) res = max(res, item.second);

        return res;
    }
};

Time complexity is O(n²)

Space complexity is O(n²)