LeetCode 835 - Image Overlap

This problem asks us to determine the maximum overlap between two binary square matrices (img1 and img2) when one matrix is translated over the other. Each matrix contains only 0s and 1s, where 1 represents a filled pixel and 0 represents an empty pixel.

leetcodemediumarraymatrix

LeetCode Problem 835

Difficulty: 🟡 Medium
Topics: Array, Matrix

Solution

Problem Understanding

This problem asks us to determine the maximum overlap between two binary square matrices (img1 and img2) when one matrix is translated over the other. Each matrix contains only 0s and 1s, where 1 represents a filled pixel and 0 represents an empty pixel. A translation means shifting all 1s in one image in any combination of up, down, left, or right directions. Any pixels that move outside the matrix boundaries are discarded. The goal is to find the translation that maximizes the number of positions where both images have a 1 simultaneously.

The inputs are two n x n matrices where 1 <= n <= 30. This small size hints that a brute-force approach may be feasible, but there may be optimizations that make the solution more elegant and faster. Edge cases include matrices with all zeros (resulting in zero overlap), matrices of size 1 x 1, or matrices with a single 1 at a corner. The problem guarantees square matrices, so we do not need to handle rectangular inputs.

Approaches

Brute Force Approach

The brute-force approach considers every possible translation of img1 over img2. For each translation, we calculate the overlap by iterating through every element in the matrices and counting positions where both have a 1. Given the maximum matrix size of 30 x 30, there are 2n-1 possible shifts in both horizontal and vertical directions. Therefore, the total number of translations is (2n-1) * (2n-1) and checking each translation requires O(n^2) time, leading to a total time complexity of O(n^4). This is correct but not very efficient.

Optimal Approach

A key insight is to treat positions of 1s as points and compute the vector offsets between all pairs of 1s from img1 and img2. For each 1 in img1 at (i1, j1) and each 1 in img2 at (i2, j2), the translation vector (i2 - i1, j2 - j1) would align these two 1s. If multiple pairs share the same translation vector, that vector corresponds to an overlap of the number of pairs. Using a hash map to count the frequency of each translation vector allows us to find the vector with the maximum overlap efficiently.

This approach significantly reduces redundant calculations and avoids iterating over every possible translation explicitly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Iterate over all translations and count overlaps
Optimal O(n^4) worst-case but faster in practice O(n^2) Use hash map to count translation vectors between 1s

Algorithm Walkthrough

  1. Extract coordinates of 1s: Iterate over both matrices and record the positions (i, j) of all 1s in img1 and img2.
  2. Compute translation vectors: For each pair of 1s (x1, y1) from img1 and (x2, y2) from img2, compute the translation vector (dx, dy) = (x2 - x1, y2 - y1).
  3. Count vector frequencies: Maintain a hash map where keys are translation vectors and values are the count of how many pairs produce that vector.
  4. Find maximum overlap: The maximum value in the hash map corresponds to the largest possible overlap.
  5. Return the result: If no 1s exist, return 0; otherwise, return the maximum count.

Why it works: Each translation vector aligns specific 1s from img1 with 1s from img2. Counting how many pairs produce the same vector directly gives the overlap for that translation. Since we examine all pairs, we consider all possible overlaps, guaranteeing correctness.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        ones_img1 = [(i, j) for i in range(n) for j in range(n) if img1[i][j] == 1]
        ones_img2 = [(i, j) for i in range(n) for j in range(n) if img2[i][j] == 1]
        
        vector_count = Counter()
        for x1, y1 in ones_img1:
            for x2, y2 in ones_img2:
                vector_count[(x2 - x1, y2 - y1)] += 1
        
        return max(vector_count.values(), default=0)

The solution first extracts coordinates of all 1s in both matrices. The nested loops compute translation vectors for each pair of 1s and increment the count in a hash map. Finally, the max function identifies the translation vector that gives the largest overlap. The default=0 ensures correctness when there are no 1s.

Go Solution

func largestOverlap(img1 [][]int, img2 [][]int) int {
    n := len(img1)
    type point struct{ x, y int }
    onesImg1 := []point{}
    onesImg2 := []point{}

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if img1[i][j] == 1 {
                onesImg1 = append(onesImg1, point{i, j})
            }
            if img2[i][j] == 1 {
                onesImg2 = append(onesImg2, point{i, j})
            }
        }
    }

    vectorCount := make(map[point]int)
    maxOverlap := 0
    for _, p1 := range onesImg1 {
        for _, p2 := range onesImg2 {
            vec := point{p2.x - p1.x, p2.y - p1.y}
            vectorCount[vec]++
            if vectorCount[vec] > maxOverlap {
                maxOverlap = vectorCount[vec]
            }
        }
    }

    return maxOverlap
}

In Go, we use a struct point to represent both coordinates and translation vectors. A map is used to count vectors, and we update the maximum overlap dynamically. Go requires explicit handling of slices and map keys, unlike Python tuples.

Worked Examples

Example 1

img1 = [[1,1,0],[0,1,0],[0,1,0]]
img2 = [[0,0,0],[0,1,1],[0,0,1]]

Coordinates of 1s:

img1: (0,0), (0,1), (1,1), (2,1)

img2: (1,1), (1,2), (2,2)

Compute translation vectors:

  • (1,1)-(0,0) = (1,1)
  • (1,2)-(0,0) = (1,2)
  • (2,2)-(0,0) = (2,2)
  • ...
  • Maximum count of a vector: (1,1) occurs 3 times → overlap = 3

Example 2

img1 = [[1]]
img2 = [[1]]

Vectors: (0,0) → overlap = 1

Example 3

img1 = [[0]]
img2 = [[0]]

No 1s → overlap = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n^4) worst-case For n x n matrices, there are at most n^2 1s in each image. Computing translation vectors for all pairs is O(n^2 * n^2)
Space O(n^2) Store coordinates of 1s and a hash map of translation vectors

The practical runtime is usually better because most matrices are sparse, and the number of 1s is much less than n^2.

Test Cases

# Provided examples
assert Solution().largestOverlap([[1,1,0],[0,1,0],[0,1,0]], [[0,0,0],[0,1,1],[0,0,1]]) == 3
assert Solution().largestOverlap([[1]], [[1]]) == 1
assert Solution().largestOverlap([[0]], [[0]]) == 0

# Edge cases
assert Solution().largestOverlap([[0,0],[0,0]], [[0,0],[0,0]]) == 0  # all zeros
assert Solution().largestOverlap([[1,0],[0,0]], [[0,0],[0,1]]) == 1  # single ones, opposite corners
assert Solution().largestOverlap([[1,1],[1,1]], [[1,1],[1,1]]) == 4  # full overlap
assert Solution().largestOverlap([[1,0,0],[0,0,0],[0,0,0]], [[0,0,1],[0,0,0],[0,0,0]]) == 1  # single ones, distant
Test Why
Example 1 Validates normal overlap with shift
Example 2 Minimal