Formatted question description: https://leetcode.ca/all/835.html
835. Image Overlap (Medium)
Two images A
and B
are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)
We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.
(Note also that a translation does not include any kind of rotation.)
What is the largest possible overlap?
Example 1:
Input: A = [[1,1,0], [0,1,0], [0,1,0]] B = [[0,0,0], [0,1,1], [0,0,1]] Output: 3 Explanation: We slide A to right by 1 unit and down by 1 unit.
Notes:
1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <= A[i][j], B[i][j] <= 1
Related Topics:
Array
Solution 1. Brute Force
// OJ: https://leetcode.com/problems/imageoverlap/
// Time: O(N^4)
// Space: O(1)
class Solution {
int overlap(vector<vector<int>> &A, vector<vector<int>> &B, int dx, int dy) {
int N = A.size(), ans = 0;
for (int i = 0; i + dx < N; ++i) {
for (int j = 0; j + dy < N; ++j) {
ans += B[i][j] == 1 && A[i + dx][j + dy] == B[i][j];
}
}
return ans;
}
public:
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int N = A.size(), ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
ans = max({ ans, overlap(A, B, i, j), overlap(B, A, i, j) });
}
}
return ans;
}
};
Solution 2. Most Common Index Distance
If the image is sparse matrix, we can save computation in the following way.
To make the problem simpler, think of two 1d arrays, we want to compute the largestOverlap
of them. We can store the indexes of 1s into two vector<int>
va
and vb
, and compute the most common distance between va[i]
and vb[j]
.
Example:
A = [1, 1, 1, 0]
B = [0, 1, 0, 1]
va = [0, 1, 2]
vb = [1, 3]
// we compute the difference between each pair of the indexes
diff = [1, 0, 1,
3, 2, 1]
frequency = {
{3, 1},
{2, 1},
{1, 2}, // 1 appeared twice
{0, 1},
{1, 1}
}
// Since 1 is the most frequent difference and its frequency is 2
// The best answer is to shift `B` by `1` and we get `2` overlaps.
For a 2d array, the distance becomes 2d as well. Instead of using pairs, we encode x, y
as 100 * x + y
thus the 2d array is flattened to 1d array, and the distance becomes 100 * delta_x + delta_y
. The most common distance is the answer.
Why using 100
instead of 30
? Since the delta_y
has range 29 = (N  1)
to 29 = (N  1)
. So using 30
will cause ambiguous intrepretation of the distance. For example, distance 15
can be interpreted as 0 * 30 + 15
and 1 * 30  15
.
The minimum value of the multiplier is the size of range of delta_y
which is (N  1)  (N  1) + 1 = 2 * N  1
.
// OJ: https://leetcode.com/problems/imageoverlap/
// Time: O(N^2+AB) where A and B are the counts of 1s in image `A` and `B`.
// Space: O(N^2+AB)
// Ref: https://leetcode.com/problems/imageoverlap/discuss/130623/C%2B%2BJavaPythonStraightForward
class Solution {
private:
vector<int> flatten(vector<vector<int>>& A) {
int N = A.size();
vector<int> ans;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i][j] == 1) ans.push_back(i * 100 + j);
}
}
return ans;
}
public:
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
auto va = flatten(A), vb = flatten(B);
unordered_map<int, int> m;
for (int i : va) {
for (int j : vb) {
m[i  j]++;
}
}
int ans = 0;
for (auto p : m) ans = max(ans, p.second);
return ans;
}
};
Java

class Solution { public int largestOverlap(int[][] A, int[][] B) { int maxOverlap = 0; int sideLength = A.length; int maxMove = sideLength  1; for (int i = maxMove; i <= maxMove; i++) { for (int j = maxMove; j <= maxMove; j++) { int overlap = 0; int rowStart = Math.max(0, i), rowEnd = Math.min(sideLength, sideLength + i); int columnStart = Math.max(0, j), columnEnd = Math.min(sideLength, sideLength + j); for (int row = rowStart; row < rowEnd; row++) { for (int column = columnStart; column < columnEnd; column++) { if (A[row][column] == 1 && B[row  i][column  j] == 1) overlap++; } } maxOverlap = Math.max(maxOverlap, overlap); } } return maxOverlap; } }

// OJ: https://leetcode.com/problems/imageoverlap/ // Time: O(N^4) // Space: O(1) class Solution { int overlap(vector<vector<int>> &A, vector<vector<int>> &B, int dx, int dy) { int N = A.size(), ans = 0; for (int i = 0; i + dx < N; ++i) { for (int j = 0; j + dy < N; ++j) { ans += B[i][j] == 1 && A[i + dx][j + dy] == B[i][j]; } } return ans; } public: int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) { int N = A.size(), ans = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ans = max({ ans, overlap(A, B, i, j), overlap(B, A, i, j) }); } } return ans; } };

class Solution: def largestOverlap(self, A, B): """ :type A: List[List[int]] :type B: List[List[int]] :rtype: int """ N = len(A) LA = [(xi, yi) for xi in range(N) for yi in range(N) if A[xi][yi]] LB = [(xi, yi) for xi in range(N) for yi in range(N) if B[xi][yi]] d = collections.Counter([(x1  x2, y1  y2) for (x1, y1) in LA for (x2, y2) in LB]) return max(d.values() or [0])