Image Overlap - Video Solutions

Problem Overview: You are given two n x n binary matrices representing images. You can translate one image in any direction (up, down, left, right). The goal is to find the maximum number of positions where both images contain 1 after a translation. Only overlapping cells count.

Approach 1: Brute Force Using Translation (Time: O(n^4), Space: O(1))

Try every possible shift of img1 relative to img2. For an n x n grid there are (2n-1)^2 possible translations. For each translation, iterate through the overlapping region and count positions where both matrices contain 1. Track the maximum overlap seen so far. The logic is straightforward: nested loops generate shifts, then another scan compares cells in the overlapping window. This approach relies purely on iteration over the array and matrix structure.

The downside is the cost of checking every translation. Each shift requires scanning up to n^2 cells, producing a total complexity of O(n^4). With the constraint n ≤ 30, this still runs comfortably in practice and is often the first solution implemented during interviews to confirm correctness.

Approach 2: Using Convolution / Cross-Correlation (Time: O(n^2 log n), Space: O(n^2))

The overlap operation is equivalent to computing the cross-correlation of the two binary matrices. Treat each matrix as a signal and compute how well one aligns with the other at every possible shift. This can be implemented using 2D convolution where one matrix is flipped and convolved with the other. Fast Fourier Transform (FFT) accelerates this process.

The key insight: convolution automatically evaluates overlap counts for every translation simultaneously. Convert both matrices into numeric grids, perform FFT-based convolution, and read the maximum value in the result grid. That value represents the maximum number of overlapping 1s. FFT reduces the computation from checking every shift manually to performing polynomial-style multiplication in the frequency domain.

This technique is common in image processing and signal analysis problems involving matrix alignment or pattern matching. It requires additional memory for frequency-domain arrays but significantly reduces runtime compared to brute-force enumeration.

Recommended for interviews: Start with the brute-force translation approach. It clearly demonstrates understanding of how image shifts affect overlap and is easy to implement under pressure. Once correctness is established, discuss convolution or correlation-based optimization. Interviewers typically expect the translation solution first, while recognizing convolution shows deeper algorithmic and mathematical awareness.