Leetcode 835. Image Overlap

Problem Explanation

Given two binary matrix images A and B, the task is to determine the largest overlap of these two images when one is translated on top of the other. Translation here means shifting left, right, up or down the entire matrix. It does not include rotation of image A or B.

Considering an example: A = [[1,1,0], [0,1,0],   [0,1,0]]  B = [[0,0,0],   [0,1,1],   [0,0,1]] In order to achieve maximum overlap, we can shift image A one step down and one step to the right. This gives us an overlap of three 1s for the two images.

Solution

We first generate the relative positions of pixels of value 1 in the original and the translated array, and then count the occurrence of the relative positions in the translated array. This is done by creating a map (unordered_map in C++, dict in Python, Map in Java and JavaScript, Dictionary in C#) where each key-value pair stands for the relative position and its occurrence.

Let's walk through the example above:

For image A, the relative positions of pixels of value 1 are: (0,0), (0,1), (1,1), (2,1). For image B, the relative positions of pixels of value 1 are: (1,1), (1,2), (2,2).

The relative positions of translation from A to B would be computed as positions in A minus positions in B: (0,0), (-1,0), (0,0), (1,0), (0,-1), (-1,-1), (0,-1), (1,-1), (0,0), (-1,0), (0,0), (1,0), which means we have (0,0) three times, (-1,0) twice, (0,-1) twice and (1,0) twice, (-1,-1) once, (1,-1) once.

So the largest possible overlap would be the most frequent relative position, which is (0,0) with a frequency of 3.

Solutions

Python

1
2python
3class Solution:
4    def largestOverlap(self, A, B):
5        import collections
6        N = len(A)
7
8        def shift(dx, dy):
9            return sum(A[i][j] == B[i-dx][j-dy] == 1 for i in range(dx,N) for j in range(dy,N))
10
11        return max(shift(dx,dy) for dx in range(N) for dy in range(N))

Java

1
2java
3class Solution {
4    public int largestOverlap(int[][] A, int[][] B) {
5        int N = A.length;
6        List<Integer> LA = new ArrayList<>();
7        List<Integer> LB = new ArrayList<>();
8        HashMap<Integer, Integer> count = new HashMap<>();
9        for (int i = 0; i < N * N; ++i)
10            if (A[i / N][i % N] == 1)
11                LA.add(i / N * 100 + i % N);
12        for (int i = 0; i < N * N; ++i)
13            if (B[i / N][i / N] == 1)
14                LB.add(i / N * 100 + i % N);
15        for (int i : LA) for (int j : LB)
16                count.put(i - j, count.getOrDefault(i - j, 0) + 1);
17        int res = 0;
18        for (int i : count.values())
19            res = Math.max(res, i);
20        return res;
21    }
22}

JavaScript

1
2javascript
3var largestOverlap = function(A, B) {
4    let count = new Map();
5    const N = A.length;
6    for(let i=0;i<N**2;++i) {
7        for(let j=0;j<N**2;++j) {
8            let countKey = "";
9            if(A[Math.trunc(i/N)][i%N] == 1 && B[Math.trunc(j/N)][j%N] == 1)
10                countKey = Math.trunc(i/N) - Math.trunc(j/N) + " " + ((i%N) - (j%N) );
11            if(countKey)
12                count.set(countKey, (count.get(countKey) || 0) + 1);
13        }
14    }
15    let maxOverlap = 0;
16    count.forEach(value => maxOverlap = Math.max(maxOverlap, value));
17    return maxOverlap;
18};

C++

1
2cpp
3class Solution {
4public:
5    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
6        int N = A.size(), res = 0;
7        vector<int> LA, LB;
8        unordered_map<int, int> count;
9        for (int i = 0; i < N * N; ++i)
10            if (A[i / N][i % N] == 1)
11                LA.push_back(i / N * 100 + i % N);
12        for (int i = 0; i < N * N; ++i)
13            if (B[i / N][i % N] == 1)
14                LB.push_back(i / N * 100 + i % N);
15        for (int i : LA) for (int j : LB)
16                res = max(res, ++count[i - j]);
17        return res;
18    }
19};

C#

1
2csharp
3public class Solution {
4    public int LargestOverlap(int[][] A, int[][] B) {
5        int N = A.Length, res = 0;
6        List<int> LA = new List<int>(), LB = new List<int>();
7        Dictionary<int, int> count = new Dictionary<int, int>();
8        for (int i = 0; i < N * N; ++i)
9            if (A[i / N][i % N] == 1)
10                LA.Add(i / N * 100 + i % N);
11        for (int i = 0; i < N * N; ++i)
12            if (B[i / N][i % N] == 1)
13                LB.Add(i / N * 100 + i % N);
14        foreach (int i in LA) foreach (int j in LB)
15                if (!count.ContainsKey(i - j)) count[i - j] = 0;
16                res = Math.Max(res, ++count[i - j]);
17        return res;
18    }
19}

Solution Explanation

In our solution, we compute the relative positions of each '1' in both arrays, then for each pixel of value '1' in A and B, compute the relative position in the translated array and count the occurrence of each relative position.

This solution is straightforward and concise without any nested loop explicitly in the source code of the solution. The implicit nested loop is done by the built-in function, which is usually optimized.

The time complexity is O(n^4) in the worst case when all values are 1 in the matrices, where n is the size of the input matrix. In the average case, the time complexity would depend on the number of 1s in the matrix.

The space complexity of the algorithm is O(n^2), where n is the size of input matrix. This is required for storing the elements of the matrix.

In summary, our solution provides a neat and efficient way to solve this problem, leveraging the features of the language for better performance while maintaining code readability.