Scale Engineer

Image Overlap

Med
#0789Time: O(n^4). There are `O(n^2)` possible translations (`(2n-1) * (2n-1)`). For each translation, we iterate through the `n x n` grid to count the overlap, which takes `O(n^2)` time.Space: O(1). We only use a few variables to store the shifts and counts, so the space is constant.
Data structures
ArrayMatrix

Prompt

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].length
  • n == img2.length == img2[i].length
  • 1 <= n <= 30
  • img1[i][j] is either 0 or 1.
  • img2[i][j] is either 0 or 1.

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward approach. We can simulate every possible translation of img1 and, for each translation, count the number of overlapping 1s with img2. The maximum count found among all translations is the answer.

Algorithm

  • Initialize maxOverlap = 0.
  • Get the dimension n of the images.
  • Loop for vertical shift dy from -(n-1) to n-1.
  • Loop for horizontal shift dx from -(n-1) to n-1.
    • Initialize currentOverlap = 0.
    • Loop for row r from 0 to n-1.
    • Loop for column c from 0 to n-1.
      • Calculate the translated coordinates in img2: tr = r + dy and tc = c + dx.
      • Check if (tr, tc) is within the bounds of the n x n grid.
      • If it is, and both img1[r][c] and img2[tr][tc] are 1, increment currentOverlap.
    • Update maxOverlap = max(maxOverlap, currentOverlap).
  • Return maxOverlap.

Walkthrough

We consider all possible relative translations between the two images. A translation can be represented by a vector (dx, dy), where dx is the horizontal shift and dy is the vertical shift.

To ensure we cover all possibilities of overlap, the shifts dx and dy must range from -(n-1) to n-1, where n is the dimension of the matrix. This gives (2n-1) * (2n-1) possible translations.

For each translation (dx, dy):

  • We initialize a counter for the current overlap to zero.
  • We iterate through every cell (r, c) of img1.
  • We calculate the corresponding cell's coordinates (r + dy, c + dx) in img2's grid.
  • If this translated coordinate is within the bounds of img2 (i.e., 0 <= r + dy < n and 0 <= c + dx < n), and both img1[r][c] and img2[r + dy][c + dx] are 1, we increment the overlap counter.

We keep track of the maximum overlap found across all translations and return it.

class Solution {    public int largestOverlap(int[][] img1, int[][] img2) {        int n = img1.length;        int maxOverlap = 0;         for (int dy = -n + 1; dy < n; dy++) {            for (int dx = -n + 1; dx < n; dx++) {                maxOverlap = Math.max(maxOverlap, countOverlap(img1, img2, dx, dy));            }        }        return maxOverlap;    }     private int countOverlap(int[][] img1, int[][] img2, int dx, int dy) {        int n = img1.length;        int count = 0;        for (int r = 0; r < n; r++) {            for (int c = 0; c < n; c++) {                int tr = r + dy;                int tc = c + dx;                 if (tr >= 0 && tr < n && tc >= 0 && tc < n) {                    if (img1[r][c] == 1 && img2[tr][tc] == 1) {                        count++;                    }                }            }        }        return count;    }}

Complexity

Time

O(n^4). There are `O(n^2)` possible translations (`(2n-1) * (2n-1)`). For each translation, we iterate through the `n x n` grid to count the overlap, which takes `O(n^2)` time.

Space

O(1). We only use a few variables to store the shifts and counts, so the space is constant.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra space.

Cons

  • Very inefficient, especially for larger n.

  • Performs many redundant checks on cells that contain 0s and cannot contribute to the overlap.

Solutions

class Solution {public  int largestOverlap(int[][] img1, int[][] img2) {    int n = img1.length;    Map<List<Integer>, Integer> cnt = new HashMap<>();    int ans = 0;    for (int i = 0; i < n; ++i) {      for (int j = 0; j < n; ++j) {        if (img1[i][j] == 1) {          for (int h = 0; h < n; ++h) {            for (int k = 0; k < n; ++k) {              if (img2[h][k] == 1) {                List<Integer> t = List.of(i - h, j - k);                ans = Math.max(ans, cnt.merge(t, 1, Integer : : sum));              }            }          }        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem