Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

835. Image Overlap - Leetcode Solution

Code Implementation

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        ones_img1 = []
        ones_img2 = []
        for i in range(n):
            for j in range(n):
                if img1[i][j] == 1:
                    ones_img1.append((i, j))
                if img2[i][j] == 1:
                    ones_img2.append((i, j))
        from collections import Counter
        count = Counter()
        for (x1, y1) in ones_img1:
            for (x2, y2) in ones_img2:
                shift = (x2 - x1, y2 - y1)
                count[shift] += 1
        return max(count.values() or [0])
      
class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        vector<pair<int, int>> ones_img1, ones_img2;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j] == 1) ones_img1.push_back({i, j});
                if (img2[i][j] == 1) ones_img2.push_back({i, j});
            }
        }
        map<pair<int, int>, int> count;
        int res = 0;
        for (auto& p1 : ones_img1) {
            for (auto& p2 : ones_img2) {
                pair<int, int> shift = {p2.first - p1.first, p2.second - p1.second};
                count[shift]++;
                res = max(res, count[shift]);
            }
        }
        return res;
    }
};
      
class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        List<int[]> onesImg1 = new ArrayList<>();
        List<int[]> onesImg2 = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j] == 1) onesImg1.add(new int[]{i, j});
                if (img2[i][j] == 1) onesImg2.add(new int[]{i, j});
            }
        }
        Map<String, Integer> count = new HashMap<>();
        int res = 0;
        for (int[] p1 : onesImg1) {
            for (int[] p2 : onesImg2) {
                int dx = p2[0] - p1[0], dy = p2[1] - p1[1];
                String key = dx + "," + dy;
                count.put(key, count.getOrDefault(key, 0) + 1);
                res = Math.max(res, count.get(key));
            }
        }
        return res;
    }
}
      
var largestOverlap = function(img1, img2) {
    const n = img1.length;
    const ones1 = [], ones2 = [];
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (img1[i][j] === 1) ones1.push([i, j]);
            if (img2[i][j] === 1) ones2.push([i, j]);
        }
    }
    let count = {};
    let res = 0;
    for (let [x1, y1] of ones1) {
        for (let [x2, y2] of ones2) {
            let key = (x2 - x1) + ',' + (y2 - y1);
            count[key] = (count[key] || 0) + 1;
            res = Math.max(res, count[key]);
        }
    }
    return res;
};

Problem Description

You are given two binary square matrices img1 and img2 of size n x n. Each cell contains either 0 or 1, representing a black or white pixel. You can translate img1 (slide it up, down, left, or right any number of units), but cannot rotate it. After translating, the overlap between img1 and img2 is the number of positions where both matrices have 1 in the same cell. Your task is to compute the largest possible overlap by translating img1 over img2. No elements are reused or modified; you are only allowed to shift img1. Return the maximum number of overlapping 1s possible.

Thought Process

At first glance, the problem suggests checking all possible translations of img1 and counting the number of overlapping 1s with img2 each time. For each shift, we would need to compare every cell and count the matches. While this brute-force approach works for small matrices, it quickly becomes inefficient as n grows. To optimize, we notice that only the positions containing 1 in both images matter. Instead of shifting the whole matrix, we can focus on the coordinates of 1s. For every pair of 1s (one from img1, one from img2), we can calculate the translation vector required to align them. By counting how many times each translation occurs, we can find the translation that results in the most overlaps.

Solution Approach

The optimized solution works as follows:
  • Step 1: Collect the coordinates of all 1s in both img1 and img2.
  • Step 2: For each 1 in img1, pair it with each 1 in img2 and compute the translation vector needed to overlap them. This vector is simply the difference in their row and column indices.
  • Step 3: Use a hash map (dictionary) to count how many times each translation vector occurs. Each count represents the number of overlaps that would result from that translation.
  • Step 4: The answer is the maximum value in this hash map, representing the largest overlap possible with any translation.
This approach is efficient because it only considers meaningful shifts (those that align 1s with 1s) and avoids redundant work.

Example Walkthrough

Suppose img1 and img2 are:
img1 = [[1,1,0],[0,1,0],[0,1,0]]
img2 = [[0,0,0],[0,1,1],[0,0,1]]

Step-by-step:
  • Identify all 1s in img1: (0,0), (0,1), (1,1), (2,1)
  • Identify all 1s in img2: (1,1), (1,2), (2,2)
  • For each pair, compute the shift vector (img2_row - img1_row, img2_col - img1_col):
    For example, aligning (0,0) from img1 with (1,1) from img2 gives shift (1,1).
    Repeat for all pairs, and count how many times each shift occurs.
  • After tallying, the most common shift (say, (1,1)) occurs 3 times, meaning the largest overlap possible is 3.
This process ensures we find the translation with the maximum overlap without redundant computation.

Time and Space Complexity

Brute-force approach:
  • Time: O(n4) — For every possible shift (O(n2)), compare all cells (O(n2)).
  • Space: O(1) extra (ignoring output).
Optimized approach:
  • Time: O(N1 * N2), where N1 is the number of 1s in img1 and N2 in img2. For each pair, we compute a shift and increment a counter.
  • Space: O(N1 * N2) for the hash map storing shift counts.
This is much faster, especially when the matrices are sparse.

Summary

We solved the Image Overlap problem by shifting our focus from brute-force cell-by-cell comparison to analyzing translation vectors between 1s in the images. By counting how often each translation aligns 1s, we efficiently determine the maximum overlap. This approach leverages hash maps for fast counting and avoids unnecessary computation, making it both elegant and efficient.