835 LeetCode problem solution
LeetCode problem link: 835. Image Overlap
LeetCode 835 problem description
This is Medium level problem.
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].lengthn == img2.length == img2[i].length1 <= n <= 30img1[i][j]is either0or1.img2[i][j]is either0or1.
LeetCode 835 problem: solution explanation
We use the Translation Vector Counting pattern to find how many 1s can overlap after translating one image.
First, we collect the coordinates of all 1s from img1 and img2, so we only work with relevant cells.
For every pair of 1s, one from each image, we calculate the translation vector (dx, dy) required to align them.
If several pairs produce the same translation vector, all these pairs can overlap at the same time after applying that translation.
Therefore, the number of occurrences of each (dx, dy) directly represents the overlap produced by that translation.
Since both coordinates are between 0 and n - 1, each shift is between -(n - 1) and n - 1.
This small fixed range allows us to store translation counts in an array instead of an unordered_map, avoiding hashing overhead.
We encode each (dx, dy) into a single array index and increment its frequency whenever we find the same translation.
The largest frequency among all translation vectors is the maximum possible overlap.
We have k1 is the number of 1s in img1 and k2 is the number of 1s in img2.
In C++ solution, for example, ones1 is a vector that stores the coordinates of these k1 ones.
Therefore ones1.size() = k1 and ones2.size() = k2. And because of these two nested loops, we get k1 * k2 comparisons:
for(auto [r1, c1] : ones1)
for(auto [r2, c2] : ones2)If the images contain k1 and k2 ones, the solution takes O(n² + k1 * k2) time, which becomes O(n4) in the worst case when both images contain only 1s.
However, the constraint is only n <= 30, so even n4 is at most 30n4 = 810,000 pair comparisons, which is completely acceptable.
The translation-count array contains O(n2) possible shifts, so the space complexity is O(n2).
Time complexity: O(n2 + k1 * k2)
Space complexity: O(n2)
In worst case:
Time complexity: O(n4)
Space complexity: O(n2)
LeetCode 835 C++ solution
class Solution {
public:
int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
int n = img1.size();
vector<pair<int, int>> ones1;
vector<pair<int, int>> ones2;
for(int r = 0; r < n; r++)
{
for(int c = 0; c < n; c++)
{
if(img1[r][c]) ones1.push_back({r, c});
if(img2[r][c]) ones2.push_back({r, c});
}
}
int size = 2 * n - 1;
vector<int> count(size * size, 0);
int result = 0;
for(auto [r1, c1] : ones1)
{
for(auto [r2, c2] : ones2)
{
int dx = r2 - r1 + n - 1;
int dy = c2 - c1 + n - 1;
int key = dx * size + dy;
result = max(result, ++count[key]);
}
}
return result;
}
};LeetCode 835 Java solution
class Solution {
public int largestOverlap(int[][] img1, int[][] img2) {
int n = img1.length;
List<int[]> ones1 = new ArrayList<>();
List<int[]> ones2 = new ArrayList<>();
for(int r = 0; r < n; r++) {
for(int c = 0; c < n; c++) {
if(img1[r][c] == 1) ones1.add(new int[]{r, c});
if(img2[r][c] == 1) ones2.add(new int[]{r, c});
}
}
int size = 2 * n - 1;
int[] count = new int[size * size];
int result = 0;
for(int[] p1 : ones1) {
for(int[] p2 : ones2) {
int dx = p2[0] - p1[0] + n - 1;
int dy = p2[1] - p1[1] + n - 1;
int key = dx * size + dy;
result = Math.max(result, ++count[key]);
}
}
return result;
}
}LeetCode 835 JavaScript solution
var largestOverlap = function(img1, img2) {
const n = img1.length;
const ones1 = [];
const ones2 = [];
for(let r = 0; r < n; r++) {
for(let c = 0; c < n; c++) {
if(img1[r][c] === 1) ones1.push([r, c]);
if(img2[r][c] === 1) ones2.push([r, c]);
}
}
const size = 2 * n - 1;
const count = new Array(size * size).fill(0);
let result = 0;
for(const [r1, c1] of ones1) {
for(const [r2, c2] of ones2) {
const dx = r2 - r1 + n - 1;
const dy = c2 - c1 + n - 1;
const key = dx * size + dy;
count[key]++;
result = Math.max(result, count[key]);
}
}
return result;
};LeetCode 835 TypeScript solution
function largestOverlap(img1: number[][], img2: number[][]): number {
const n = img1.length;
const ones1: number[][] = [];
const ones2: number[][] = [];
for(let r = 0; r < n; r++) {
for(let c = 0; c < n; c++) {
if(img1[r][c] === 1) ones1.push([r, c]);
if(img2[r][c] === 1) ones2.push([r, c]);
}
}
const size = 2 * n - 1;
const count: number[] = new Array(size * size).fill(0);
let result = 0;
for(const [r1, c1] of ones1) {
for(const [r2, c2] of ones2) {
const dx = r2 - r1 + n - 1;
const dy = c2 - c1 + n - 1;
const key = dx * size + dy;
count[key]++;
result = Math.max(result, count[key]);
}
}
return result;
}LeetCode 835 Python solution
class Solution:
def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
n = len(img1)
ones1 = []
ones2 = []
for r in range(n):
for c in range(n):
if img1[r][c] == 1:
ones1.append((r, c))
if img2[r][c] == 1:
ones2.append((r, c))
size = 2 * n - 1
count = [0] * (size * size)
result = 0
for r1, c1 in ones1:
for r2, c2 in ones2:
dx = r2 - r1 + n - 1
dy = c2 - c1 + n - 1
key = dx * size + dy
count[key] += 1
result = max(result, count[key])
return result