Image Overlap

Image Overlap

What is this problem about?

The Image Overlap coding problem provides two $n imes n$ binary matrices, $A$ and $B$. You can slide matrix $A$ in any direction (up, down, left, right) over matrix $B$. After any shift, you count the number of positions where both matrices have a 1. Your goal is to find the maximum possible overlap count.

Why is this asked in interviews?

Google asks this to evaluate a candidate's ability to optimize geometric simulations. A naive approach of trying every possible shift ($2n imes 2n$) and then comparing matrices ($n^2$) results in $O(n^4)$ complexity. For $n=30$, this is fine, but interviewers want to see if you can use Coordinate Mapping to focus only on the relevant points (the 1s), which is a common strategy in image processing and computer vision.

Algorithmic pattern used

The problem uses Coordinate Differencing and a Frequency Map.

1. List the coordinates $(r, c)$ of all 1s in matrix $A$ and all 1s in matrix $B$.
2. Iterate through every pair of 1s: $(r_a, c_a)$ from $A$ and $(r_b, c_b)$ from $B$.
3. Calculate the "shift vector" required to align these two 1s: $V = (r_b - r_a, c_b - c_a)$.
4. Use a Hash Map to count the frequency of each unique shift vector.
5. The shift vector that appears most frequently represents the translation that maximizes the overlap.

Example explanation

Matrix A has 1s at: (0,0) and (1,1). Matrix B has 1s at: (1,1) and (2,2).

1. Pair (0,0) and (1,1): Shift = (1, 1).
2. Pair (0,0) and (2,2): Shift = (2, 2).
3. Pair (1,1) and (1,1): Shift = (0, 0).
4. Pair (1,1) and (2,2): Shift = (1, 1). Shift (1, 1) appears twice. Max overlap = 2.

Common mistakes candidates make

• Brute Force Simulation: Implementing the $O(n^4)$ nested loop which is much harder to get right due to boundary checks for each shift.
• Coordinate Encoding: Not using a proper key for the Hash Map (e.g., using a string "dr,dc" instead of a unique integer like dr * 100 + dc).
• Ignoring Sparse Data: Failing to realize that if the number of 1s is small, the coordinate approach is vastly superior.

Interview preparation tip

When dealing with translations or "alignments" of points, think about the difference between coordinates. If multiple pairs share the same difference vector, they will all overlap under that specific translation. This is a foundational trick in geometry and pattern matching.