Image Overlap

medium array math matrix

Problem

Two n × n binary images img1 and img2. You may translate img1 (slide left/right/up/down, no rotation) and overlay it on img2. Return the maximum number of cells where both contain 1.

Inputimg1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]

Output3

Shifting img1 right by 1 and down by 1 aligns three 1s onto img2.

img1 (rows ; cells ,)

img2 (rows ; cells ,)

from collections import Counter

def largest_overlap(img1, img2):
    n = len(img1)
    a = [(r, c) for r in range(n) for c in range(n) if img1[r][c]]
    b = [(r, c) for r in range(n) for c in range(n) if img2[r][c]]
    cnt = Counter((br - ar, bc - ac) for ar, ac in a for br, bc in b)
    return max(cnt.values(), default=0)

function largestOverlap(img1, img2) {
  const n = img1.length;
  const a = [], b = [];
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
    if (img1[r][c]) a.push([r, c]);
    if (img2[r][c]) b.push([r, c]);
  }
  const cnt = new Map();
  for (const [ar, ac] of a) for (const [br, bc] of b) {
    const key = (br - ar) + "," + (bc - ac);
    cnt.set(key, (cnt.get(key) || 0) + 1);
  }
  let best = 0;
  for (const v of cnt.values()) best = Math.max(best, v);
  return best;
}

class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
            if (img1[r][c] == 1) a.add(new int[]{r, c});
            if (img2[r][c] == 1) b.add(new int[]{r, c});
        }
        Map<Long, Integer> cnt = new HashMap<>();
        for (int[] p : a) for (int[] q : b) {
            long key = ((long)(q[0] - p[0]) & 0xffff) | (((long)(q[1] - p[1]) & 0xffff) << 16);
            cnt.merge(key, 1, Integer::sum);
        }
        int best = 0;
        for (int v : cnt.values()) best = Math.max(best, v);
        return best;
    }
}

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        vector<pair<int, int>> a, b;
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
            if (img1[r][c]) a.push_back({r, c});
            if (img2[r][c]) b.push_back({r, c});
        }
        unordered_map<long, int> cnt;
        for (auto& p : a) for (auto& q : b) {
            long key = ((long)(q.first - p.first) & 0xffff) | (((long)(q.second - p.second) & 0xffff) << 16);
            cnt[key]++;
        }
        int best = 0;
        for (auto& kv : cnt) best = max(best, kv.second);
        return best;
    }
};

Explanation

We are allowed to slide one image around (no rotating) and want the shift that lines up the most 1-cells. The neat trick is to realize that every overlap corresponds to a specific translation, so we just count which translation is the most popular.

First we collect the coordinates of all the 1 cells from each image into lists a (from img1) and b (from img2). We can ignore the zeros entirely since they never contribute to overlap.

Then for every pair — one 1-cell from img1 and one from img2 — we compute the shift (dr, dc) = (br - ar, bc - ac) that would move the first cell onto the second. We tally each shift in a counter. If a particular shift appears k times, it means that sliding img1 by that amount makes k ones land on ones.

The answer is simply the largest count in the map, because the most frequent translation gives the maximum overlap.

Example: in the sample, the shift "right 1, down 1" shows up 3 times among the pairs, so the best overlap is 3.

Time: O(n⁴) Space: O(n²)