You are given two binary square matrices img1 and img2 of size n x n, containing only 0s and 1s.

Your task:

Slide one image over the other (up, down, left, right) and determine the maximum number of overlapping 1’s.

Example:

Input:
img1 = [[1,1,0],
        [0,1,0],
        [0,1,0]]

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

Output: 3

Explanation:
A shift exists that causes 3 overlapping 1s.

---

Problem Understanding

Key characteristics:

• You can shift either image in any direction.
• Only overlapping positions counted.
• No rotation — only translations allowed.
• Overlap value = number of positions where both matrices have value 1.
• Output is the maximum overlap over all possible shifts.

Brute force idea:

• Try all possible shifts
• Count overlaps for each shift
• Return maximum

Constraints allow this:

n ≤ 30

So brute force is acceptable with optimizations.

---

Logic Explained in Simple English

Here’s the easiest way to think about solving it:

1. Look at positions in img1 where value is 1
2. Look at positions in img2 where value is 1
3. For each pair of 1s (one from each grid), compute the shift vector needed to align them
4. Count how many pairs produce the same shift
5. The shift with the highest frequency gives the maximum overlap

Why this works:

• Instead of sliding matrices physically, we count how many 1’s would match under each translation
• The most common shift is the one that aligns the most 1’s

This avoids repeatedly recomputing overlap via nested loops.

---

Step-by-Step Approach

1. Create two lists:
   • ones1 containing coordinates of 1’s in img1
   • ones2 containing coordinates of 1’s in img2
2. For every coordinate a in ones1 and every coordinate b in ones2:
   • compute shift vector (dx, dy) = (a.x - b.x, a.y - b.y)
3. Use a hashmap to count how many times each (dx, dy) occurs
4. Track maximum frequency
5. Return maximum frequency

This works because:

• Each shared shift aligns corresponding 1’s
• Counting all such yields exact maximum overlap

---

Java Implementation

class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        List<int[]> ones1 = new ArrayList<>();
        List<int[]> ones2 = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (img1[i][j] == 1) ones1.add(new int[]{i, j});
                if (img2[i][j] == 1) ones2.add(new int[]{i, j});
            }
        }
        
        Map<String, Integer> shiftCount = new HashMap<>();
        int maxOverlap = 0;
        
        for (int[] a : ones1) {
            for (int[] b : ones2) {
                int dx = a[0] - b[0];
                int dy = a[1] - b[1];
                String key = dx + "," + dy;
                int count = shiftCount.getOrDefault(key, 0) + 1;
                shiftCount.put(key, count);
                maxOverlap = Math.max(maxOverlap, count);
            }
        }
        
        return maxOverlap;
    }
}

---

Dry Run Example

img1 1 locations:

(0,0), (0,1), (1,1), (2,1)

img2 1 locations:

(1,1), (1,2), (2,2)

Compute shifts (show key ones):

Example pair:

img1(0,1) with img2(1,2):
dx = -1, dy = -1

Track frequencies:

Shift (-1,-1) occurs 3 times, meaning:

3 pairs of 1s align under that shift

Final output:

3

---

Time and Space Complexity

Time Complexity

O(k1 * k2)

Where k1 and k2 are number of 1’s in each matrix
Worst case all are 1s → O(n² * n²) = O(n⁴)

But since n ≤ 30, still fine.

Space Complexity

O(k1 * k2)

For hashmap of shifts

---

Common Mistakes and How to Avoid Them

Mistake 1: Sliding matrices physically and recounting each time

Very slow — unnecessary recomputation.

Mistake 2: Forgetting that only 1s matter

Zeros do not contribute; skip them.

Mistake 3: Using too large shift range

Shift computed automatically from coordinates.

Mistake 4: Confusing dx, dy direction

Consistently compute img1 - img2.

Mistake 5: Returning number of shifts instead of max count

Return maximum frequency of shift, not total shifts.