Image Overlap

Medium
1557.

Image Overlap

Image Overlap is a medium coding problem on arrays, matrix and enumeration, asked in Amazon, Google and Microsoft interviews.

img1 and img2 are two binary images, each an n x n matrix of 0s and 1s.

You may translate img1 — slide it any number of cells left, right, up and/or down (no rotation) — and then lay it over img2. Cells that slide outside the n x n frame are dropped. The overlap is the number of positions where both images hold a 1.

Return the largest overlap over every possible translation.

Example 1

Input
img1 = [[1,1,0],[0,1,0],[0,0,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output
3
Explanation
Slide `img1` one cell right and one cell down: all three of its 1s land on 1s of `img2`.

Example 2

Input
img1 = [[1,0],[1,1]], img2 = [[1,1],[0,1]]
Output
2

Example 3

Input
img1 = [[0]], img2 = [[0]]
Output
0

Constraints

  • n == img1.length == img1[i].length
  • n == img2.length == img2[i].length
  • 1 <= n <= 30
  • img1[i][j] is 0 or 1
  • img2[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} img1
 * @param {number[][]} img2
 * @return {number}
 */
var largestOverlap = function(img1, img2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Image Overlap — Solution in Python, Java & C++

Image Overlap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.

Image Overlap is a medium coding problem on arrays, matrix and enumeration, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Enumeration
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

img1 and img2 are two binary images, each an n x n matrix of 0s and 1s.

You may translate img1 — slide it any number of cells left, right, up and/or down (no rotation) — and then lay it over img2. Cells that slide outside the n x n frame are dropped. The overlap is the number of positions where both images hold a 1.

Return the largest overlap over every possible translation.

Example 1

Input: img1 = [[1,1,0],[0,1,0],[0,0,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: Slide `img1` one cell right and one cell down: all three of its 1s land on 1s of `img2`.

Example 2

Input: img1 = [[1,0],[1,1]], img2 = [[1,1],[0,1]]
Output: 2

Example 3

Input: img1 = [[0]], img2 = [[0]]
Output: 0

Constraints

  • n == img1.length == img1[i].length
  • n == img2.length == img2[i].length
  • 1 <= n <= 30
  • img1[i][j] is 0 or 1
  • img2[i][j] is 0 or 1

Hints for Image Overlap

  1. Hint 1

    A translation is a vector (dr, dc) with each component between -(n-1) and n-1.

  2. Hint 2

    A 1 at (i, j) in img1 and a 1 at (r, c) in img2 line up under exactly one translation: (r - i, c - j).

  3. Hint 3

    Pair every 1 of img1 with every 1 of img2, count how often each translation vector occurs, and return the largest count.

How to solve Image Overlap

Instead of trying every shift and counting overlaps, let each pair of 1s vote for the single shift that aligns them; the most-voted shift is the answer and its vote count is the overlap.

Approach

  1. List the coordinates of the 1s in img1 and in img2.
  2. For every pair (one from each list), compute (r - i + n - 1, c - j + n - 1) and increment that cell of a (2n-1) × (2n-1) counter.
  3. Return the largest counter value (0 if either image has no 1s).

Why it works

Under translation (dr, dc) the overlap is the number of 1s (i, j) of img1 whose shifted position (i + dr, j + dc) is a 1 of img2 — exactly the number of pairs that voted for (dr, dc). A shifted cell that leaves the frame cannot hit a 1 of img2, so the dropped cells never cast votes.

Complexity

  • Time — O(n⁴) in the worst case (all ones), typically much less
  • Space — O(n²)

Pitfalls

  • Shifts are in both directions — negative offsets matter as much as positive ones.
  • Offset the vector by n - 1 before using it as an array index.
  • The images are not wrapped around; cells pushed out of the frame are lost.

Reference solution

Python

from typing import List

def largestOverlap(img1: List[List[int]], img2: List[List[int]]) -> int:
    n = len(img1)
    a = [(i, j) for i in range(n) for j in range(n) if img1[i][j] == 1]
    b = [(i, j) for i in range(n) for j in range(n) if img2[i][j] == 1]
    size = 2 * n - 1
    count = [0] * (size * size)
    best = 0
    for ai, aj in a:
        for bi, bj in b:
            k = (bi - ai + n - 1) * size + (bj - aj + n - 1)
            count[k] += 1
            if count[k] > best:
                best = count[k]
    return best

Java

public static int largestOverlap(int[][] img1, int[][] img2) {
    int n = img1.length, size = 2 * n - 1;
    List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (img1[i][j] == 1) a.add(new int[]{i, j});
            if (img2[i][j] == 1) b.add(new int[]{i, j});
        }
    }
    int[] count = new int[size * size];
    int best = 0;
    for (int[] p : a) {
        for (int[] q : b) {
            int k = (q[0] - p[0] + n - 1) * size + (q[1] - p[1] + n - 1);
            if (++count[k] > best) best = count[k];
        }
    }
    return best;
}

C++

int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
    int n = img1.size(), size = 2 * n - 1;
    vector<pair<int, int>> a, b;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (img1[i][j] == 1) a.push_back({i, j});
            if (img2[i][j] == 1) b.push_back({i, j});
        }
    }
    vector<int> count(size * size, 0);
    int best = 0;
    for (auto& p : a) {
        for (auto& q : b) {
            int k = (q.first - p.first + n - 1) * size + (q.second - p.second + n - 1);
            best = max(best, ++count[k]);
        }
    }
    return best;
}

JavaScript

var largestOverlap = function(img1, img2) {
    var n = img1.length, size = 2 * n - 1;
    var ar = [], ac = [], br = [], bc = [];
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            if (img1[i][j] === 1) { ar.push(i); ac.push(j); }
            if (img2[i][j] === 1) { br.push(i); bc.push(j); }
        }
    }
    var count = new Array(size * size).fill(0), best = 0;
    for (var x = 0; x < ar.length; x++) {
        for (var y = 0; y < br.length; y++) {
            var k = (br[y] - ar[x] + n - 1) * size + (bc[y] - ac[x] + n - 1);
            count[k]++;
            if (count[k] > best) best = count[k];
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal