835. Image Overlap

This is a nice step up from Rectangle Overlap — same "translate and compare" flavor, but on grids of 0s and 1s, and it introduces a slick "count shift vectors" trick. Let's build it from zero.

---

1. Problem in Very Simple Language

You have two square grids of the same size, INLINECODE0 and INLINECODE1, each filled with INLINECODE2s and INLINECODE3s. Think of the INLINECODE4s as "lit pixels" and INLINECODE5s as "dark pixels."

You're allowed to slide (translate) one entire image — left, right, up, or down, by any whole number of steps — and then lay it on top of the other image. Sliding never rotates or flips anything, it just shifts every INLINECODE6 bit by the same amount in the same direction. Any INLINECODE7s that get pushed off the edge of the grid during this slide simply disappear (they're erased, not wrapped around).

After sliding (by whichever amount you choose) and overlaying, you count how many grid positions have a INLINECODE8 in both images at once — that's the "overlap" for that particular slide.

Goal: find the slide (shift amount) that produces the largest possible overlap count. What's given: two INLINECODE9 binary grids. What to find: the best possible shift of one grid relative to the other, to maximize matching INLINECODE10-positions. What to return: that maximum overlap count.

---

2. Real-Life Analogy

Imagine two transparent sheets of graph paper, each with some squares colored in black (the INLINECODE11s) and the rest left blank (the INLINECODE12s). You can slide one sheet around — left, right, up, down, any distance — and then stack it directly on top of the other sheet (still keeping both sheets facing the same way, no rotating or flipping). You want to find the sliding position where the most black squares from sheet A land exactly on top of black squares from sheet B.

---

3. Important Programming Concepts I Need First

2D Array / Grid

Concept: A grid of values, indexed by row and column, INLINECODE13. Why we need it: Both INLINECODE14 and INLINECODE15 are given as INLINECODE16 grids.

Translation (Shift) Vector

Concept: A translation is described by two numbers: INLINECODE17 (how far to shift horizontally — columns) and INLINECODE18 (how far to shift vertically — rows). A single point INLINECODE19 moves to INLINECODE20 after this shift. Example: Shifting by INLINECODE21 moves the point INLINECODE22 to INLINECODE23. Why we need it: The entire problem is about finding the best single shift vector to apply to one whole image.

Coordinates of INLINECODE24s (as a list of points)

Concept: Instead of thinking about a grid as a big 2D block, we can instead just list out where the INLINECODE25s are — as a collection of INLINECODE26 coordinate pairs. Everywhere else is implicitly INLINECODE27 and can be ignored. Why we need it: Since only INLINECODE28-positions can ever contribute to an overlap (a INLINECODE29 overlapping anything is never counted), we only actually care about the INLINECODE30s' locations — not the full grid.

Pairing up points from two lists, and computing their relative offset

Concept: If you have a INLINECODE31 at position INLINECODE32 in INLINECODE33, and a INLINECODE34 at position INLINECODE35 in INLINECODE36, then the specific shift that would move INLINECODE37 exactly onto INLINECODE38 is INLINECODE39 (subtracting row from row, column from column). If we later actually apply that shift to the entire INLINECODE40, this particular pair would indeed land on top of each other. Why we need it: This is the heart of the algorithm — see Section 7.

HashMap for counting occurrences

Concept: A INLINECODE41 lets us associate a "key" with a "value," and quickly look up or update that value later. Here, we'll use a shift vector (packaged as a single key, like INLINECODE42, encoded into an integer) as the key, and "how many INLINECODE43-pairs would align under this exact shift" as the value. Why we need it: Many different pairs of INLINECODE44s might all happen to require the same shift vector to align — we want to count, for each distinct possible shift, how many pairs it would successfully align, and then find the shift with the highest such count.

---

4. Understand the Input

Take Example 1: CODEBLOCK0

INLINECODE45's INLINECODE46s are located at: INLINECODE47. INLINECODE48's INLINECODE49s are located at: INLINECODE50. We want to find some shift INLINECODE51 such that, after moving every INLINECODE52 of INLINECODE53 by that same amount, the number of resulting positions that also hold a INLINECODE54 in INLINECODE55 is as large as possible. Why does it matter that we listed out just the INLINECODE56 positions, rather than looking at the whole 3×3 grid? Because the INLINECODE57 cells can never contribute to an overlap count — only matching up INLINECODE58-with-INLINECODE59 matters, so we can completely ignore the INLINECODE60s from the very start.

---

5. Understand the Output

Output: INLINECODE61

The explanation says: shift INLINECODE62 right by 1 and down by 1 — that's a shift vector of INLINECODE63. Let's verify: applying INLINECODE64 to each of INLINECODE65's INLINECODE66-positions: INLINECODE67 — is INLINECODE68 a INLINECODE69 in INLINECODE70? Yes! INLINECODE71 — is INLINECODE72 a INLINECODE73 in INLINECODE74? Yes! INLINECODE75 — is INLINECODE76 a INLINECODE77 in INLINECODE78? Yes! INLINECODE79 — this is now outside the 3×3 grid (row 3 doesn't exist for a 3-row grid, indices 0-2 only) — this INLINECODE80 gets erased, contributing nothing. Matches found: 3 (the first three). ✔️ matches the expected output!

---

6. Solve the Example Manually

Let's manually work through the logic behind why INLINECODE81 turns out to be the best shift, by considering every pair of (an INLINECODE82 1-position, an INLINECODE83 1-position) and figuring out what shift each pair would "vote for."

INLINECODE84's 1s: INLINECODE85. INLINECODE86's 1s: INLINECODE87.

For every pair INLINECODE88, the shift that would align them is INLINECODE89 (row difference, column difference):

Now let's tally up how many times each distinct shift vector appears:

INLINECODE90 appears for pairs A1-B1, A2-B2, A3-B3 → 3 times. INLINECODE91 appears for pairs A3-B2, A4-B3 → 2 times. All other shifts appear only once each.

The shift INLINECODE92 has the highest tally, 3, meaning: if we apply shift INLINECODE93 to the entire INLINECODE94, exactly 3 of its INLINECODE95s will land on INLINECODE96s in INLINECODE97 (precisely the 3 pairs that "voted" for this shift). This matches both our direct check in Section 5, and the expected output of INLINECODE98. ✔️

Why does counting "votes" per shift work? Because a specific shift INLINECODE99, when applied to the whole INLINECODE100, causes INLINECODE101 to land exactly on INLINECODE102 if and only if INLINECODE103 equals that exact shift — so the total number of INLINECODE104 INLINECODE105s that successfully land on an INLINECODE106 INLINECODE107 under a given shift is exactly the number of INLINECODE108 pairs whose difference equals that shift. Tallying all pairs' differences and taking the highest tally directly gives us the best possible shift's overlap count.

---

7. Think Like a Programmer

What do I know? For any shift INLINECODE109 applied to all of INLINECODE110, the overlap count equals the number of INLINECODE111 pairs where INLINECODE112. What do I need to find? The shift with the maximum such count. What can I try? The most direct idea: try every possible shift INLINECODE113 (ranging from INLINECODE114 to INLINECODE115 in each direction, since shifting further than that would push everything off-grid), and for each one, actually apply it to the whole grid and count matches. This is a valid, direct simulation. What happens if I try every possibility this way? There are $O(n^2)$ possible shift vectors (roughly $(2n-1) \times (2n-1)$), and for each one, checking the whole grid takes $O(n^2)$ — giving $O(n^4)$ total. For $n=30$, that's $30^4 = 810,000$ — actually still quite fast in absolute terms, but let's see if there's a cleverer, more targeted approach. Can I make it faster / more targeted? Yes — as discovered in Section 6, we don't need to try shifts "blindly" and rescan the whole grid each time. Instead, we only care about pairing up actual INLINECODE116-positions from each image and tallying up the shift each pair implies. If both images are sparse (relatively few INLINECODE117s), this can be much faster than scanning the whole grid for every candidate shift. What information should I remember? The list of INLINECODE118-positions in INLINECODE119, the list of INLINECODE120-positions in INLINECODE121, and a running tally (a INLINECODE122) of "how many pairs imply this exact shift." What pattern do I notice? This is a "vote counting" or "convolution-style" trick: instead of checking every possible transformation directly against the full data, look at every pair of "interesting" points (the INLINECODE123s) and let each pair "vote" for the specific transformation that would align it — then find the transformation with the most votes.

---

8. Start With the Brute Force Solution

Brute force idea: Try every possible shift INLINECODE124 (both ranging from INLINECODE125 to INLINECODE126). For each one, scan through every cell of INLINECODE127; if it's a INLINECODE128, compute where it would land after the shift, check if that landing spot is both within bounds and a INLINECODE129 in INLINECODE130; count all such successful landings. Track the best (maximum) count found across all shifts.

Why it works: It directly simulates the problem's description — physically trying every possible slide amount and counting the resulting overlap for each.

CODEBLOCK1

Why it's correct: It exhaustively tries every possible shift and directly counts the resulting overlap for each, exactly matching the problem's definition — guaranteed to find the true maximum.

Time complexity: $O(n^2)$ possible shifts, times $O(n^2)$ work to check each one $\rightarrow O(n^4)$. For $n=30$, that's about $810,000$ operations.

Space complexity: $O(1)$ extra memory.

---

9. Explain the Brute Force Code Line by Line

INLINECODE131 — the grid's size. INLINECODE132 — tracks the best (largest) overlap found across all tried shifts. The two outer loops (INLINECODE133, INLINECODE134) — try every possible shift amount, from INLINECODE135 to INLINECODE136 in each direction. (Shifting further than INLINECODE137 in either direction would push every INLINECODE138 off the grid, guaranteeing zero overlap, so there's no need to check beyond this range.) INLINECODE139 — resets the overlap counter for this specific shift attempt. The two inner loops (INLINECODE140, INLINECODE141) — scan every cell of INLINECODE142. INLINECODE143 — only bother checking cells that are actually INLINECODE144 (a INLINECODE145 can never contribute to overlap). INLINECODE146 — compute where this INLINECODE147 would land after applying the current shift. INLINECODE148 — check that the landing spot is still within the grid's bounds (otherwise it's erased, per the problem's rule) AND that INLINECODE149 has a INLINECODE150 there too. INLINECODE151 — if both conditions hold, this is a successful overlap; increment the count for this shift. INLINECODE152 — after fully evaluating this shift, update our overall best-so-far if this shift did better. INLINECODE153 — after trying every possible shift, return the best overlap found.

---

10. Why Might We Want Something Faster?

For $n=30$ specifically, the brute force above (INLINECODE154 operations) runs essentially instantly — there's no real performance problem here. But notice something wasteful: even when INLINECODE155 and INLINECODE156 are mostly INLINECODE157s (sparse), we're still looping over every cell of the grid, for every candidate shift, even though only the relatively few INLINECODE158-cells can ever actually matter. If $n$ were much larger, or if we wanted a more targeted approach that scales with "how many INLINECODE159s there are" rather than "how big the grid is," we'd want the pairing/voting trick from Section 6.

---

11. Find the Better (Voting) Approach

"Can we focus only on the cells that actually matter?"

Yes — using the insight from Section 6:

CODEBLOCK2

---

⭐ Key Insight

Before the insight

It seems like we need to physically try every possible shift and rescan the whole grid to measure its resulting overlap.

The problem

Most of the grid is often INLINECODE160s, which can never contribute to overlap — rescanning them repeatedly, once per candidate shift, is wasted effort.

The insight

Every possible overlapping pair (an INLINECODE161 INLINECODE162 at position INLINECODE163, an INLINECODE164 INLINECODE165 at position INLINECODE166) determines EXACTLY ONE shift — namely INLINECODE167 — that would cause INLINECODE168 to land on INLINECODE169. If we consider every such pair and tally which shift each one "votes for," then the total number of votes any particular shift receives is exactly the total overlap count that shift would produce if actually applied to the whole image (since it's counting, precisely, how many INLINECODE170 INLINECODE171s land on INLINECODE172 INLINECODE173s under that shift). So instead of testing shifts directly, we can discover the best shift (and its overlap count) purely by counting votes among pairs of INLINECODE174-positions.

After the insight

We never need to "apply" any shift to the whole grid at all — we just enumerate all INLINECODE175 pairs, compute their implied shift, tally it in a INLINECODE176, and read off the maximum tally at the end.

---

13. Dry Run the Optimized Solution

We already did the full dry run in Section 6 for Example 1 — every pair's implied shift was computed and tallied, with INLINECODE177 winning with 3 votes, matching the expected output of INLINECODE178.

Let's also quickly dry-run Example 2: INLINECODE179, INLINECODE180.

INLINECODE181's 1-positions: just INLINECODE182. INLINECODE183's 1-positions: just INLINECODE184. Only one pair to consider: INLINECODE185, implied shift = INLINECODE186. Tally: shift INLINECODE187 gets 1 vote. Maximum tally: INLINECODE188. Output: INLINECODE189 ✔️ (makes sense — no shift at all is needed, since the single INLINECODE190 is already aligned).

And Example 3: INLINECODE191, INLINECODE192. Neither image has any INLINECODE193s at all — there are no pairs to consider whatsoever, so our tally map stays completely empty. The maximum of an empty collection of tallies should be treated as INLINECODE194 (no overlap is possible, since there's nothing to overlap). Output: INLINECODE195 ✔️.

---

14. Optimized Code

CODEBLOCK3

CODEBLOCK4

---

15. Explain Optimized Code Line by Line

INLINECODE196 / INLINECODE197 — will hold the INLINECODE198 coordinates of every INLINECODE199 in each respective image. The double loop over INLINECODE200 — scans the grid once to collect all INLINECODE201-positions from both images simultaneously (a single pass does double duty here). INLINECODE202 — record this position if it's a INLINECODE203 in INLINECODE204. Same idea for INLINECODE205. INLINECODE206 — our tally: maps an encoded shift vector to how many INLINECODE207 pairs have implied that exact shift so far. INLINECODE208 — tracks the highest tally seen (which directly corresponds to the best overlap count). The nested INLINECODE209 — tries every possible pairing of an INLINECODE210 INLINECODE211-position with an INLINECODE212 INLINECODE213-position. INLINECODE214 — computes the exact shift that would move INLINECODE215 onto INLINECODE216. INLINECODE217 — since INLINECODE218 and INLINECODE219 can each range from INLINECODE220 to INLINECODE221 (so they can be negative, which doesn't work well as a raw array index or simple map key without care), we shift both by INLINECODE222 to make them non-negative (INLINECODE223 ranges from INLINECODE224 to INLINECODE225, always positive), then combine them into a single unique integer using a technique similar to how you'd flatten a 2D array index into 1D (INLINECODE226) — here using INLINECODE227 as a safely-large "width" so that different INLINECODE228 pairs never accidentally produce the same combined key. INLINECODE229 — look up how many votes this shift has received so far (or INLINECODE230 if it's never been seen), and add one more vote for the current pair. INLINECODE231 — save this updated vote count back into the map. INLINECODE232 — keep track of the highest vote count seen across all pairs processed so far — this running maximum, once every pair has been processed, is exactly our final answer (no need for a separate final pass over the map). INLINECODE233 — return the largest overlap found.

---

16. Test With Multiple Examples

Example 1 — Normal Case

INLINECODE234 → dry-ran fully in Section 6 → Output: INLINECODE235 ✔️

Example 2 — Different Case

INLINECODE236 → dry-ran in Section 13 → Output: INLINECODE237 ✔️

Example 3 — Edge Case (no 1s at all)

INLINECODE238 → dry-ran in Section 13 → Output: INLINECODE239 ✔️

---

17. Edge Cases

One or both images have no INLINECODE240s at all → no pairs exist to vote → INLINECODE241 stays empty → correctly returns the initial INLINECODE242. Both images are identical → the shift INLINECODE243 (no movement at all) will receive votes from every matching pair, and in particular, every INLINECODE244 in INLINECODE245 pairs with the same-position INLINECODE246 in INLINECODE247, so INLINECODE248 gets at least as many votes as there are INLINECODE249s total. INLINECODE250 (smallest possible grid) → only one possible cell; if both INLINECODE251 and INLINECODE252 are INLINECODE253, output is INLINECODE254; otherwise INLINECODE255 — handled correctly and trivially by the general algorithm. Very sparse images (very few INLINECODE256s in a large grid) → the voting approach shines here, since we only ever process pairs of actual INLINECODE257-positions, never wasting time on the many INLINECODE258-cells. Very dense images (most cells are INLINECODE259) → in the worst case (e.g., all cells are INLINECODE260 in both images), the number of pairs is $n^2 \times n^2 = n^4$ — the same order as the brute force's worst case, but for $n \le 30$ this remains entirely manageable either way.

---

18. Time Complexity

What is time complexity? An estimate of how the total work grows as input size grows.

CODEBLOCK5

Why: The brute-force approach always pays the full $O(n^4)$ cost, no matter how few INLINECODE261s actually exist. The voting approach's cost scales directly with how many INLINECODE262s there actually are in each image — for sparse images, this can be dramatically faster; for maximally dense images, it converges to the same worst-case bound as brute force. For this problem's specific constraint ($n \le 30$), both approaches are comfortably fast in practice, but the voting technique is the more broadly scalable and commonly-expected solution for this type of "best alignment" problem.

---

19. Space Complexity

INLINECODE263, INLINECODE264 — store up to $O(n^2)$ coordinate pairs each, in the worst case (a fully-INLINECODE265 image). INLINECODE266 — stores at most $O((2n-1)^2)$ distinct shift-key entries (since there are only that many possible distinct INLINECODE267 combinations).

Overall space: $O(n^2)$.

---

20. Common Mistakes Beginners Make

❌ "I should compute the shift as INLINECODE268 instead of INLINECODE269." ✅ We want the shift that, when applied to INLINECODE270's point INLINECODE271, lands it on INLINECODE272's point INLINECODE273 — that's INLINECODE274 (the destination minus the source). Reversing this would compute the opposite shift, effectively solving the mirror-image version of the intended question.

❌ "I can just use a INLINECODE275 like INLINECODE276 as the HashMap key, no need to encode into a single integer." ✅ This works too, and is arguably simpler to read — using an encoded integer key (as shown) is just a common performance-minded alternative that avoids the overhead of string concatenation and string-based hashing; both approaches are valid, and beginners should feel free to use whichever is clearer to them.

❌ "I need to also check the reverse direction — shifting INLINECODE277 instead of INLINECODE278." ✅ Shifting INLINECODE279 by INLINECODE280 and shifting INLINECODE281 by INLINECODE282 produce the exact same relative alignment (and thus the same overlap count) — so considering all shifts of INLINECODE283 alone (across the full range of positive and negative INLINECODE284) already covers every meaningful relative positioning.

❌ "The valid shift range should be INLINECODE285 to INLINECODE286 only (non-negative), since 'sliding' sounds like it should always move things in a positive direction." ✅ Shifts can be negative too (sliding left or up) — the full valid range is INLINECODE287 to INLINECODE288 in each direction, covering every meaningful relative offset between the two images.

❌ "If both images are empty (INLINECODE289 with all zeros, or larger all-zero grids), I should return something other than INLINECODE290, since there's 'no overlap to compute'." ✅ Zero INLINECODE291s means zero possible overlap, by definition — INLINECODE292 is exactly the correct answer, and the algorithm naturally produces it without needing any special-case handling.

---

21. How to Recognize This Pattern in Other Problems

Watch for these signal phrases:

CODEBLOCK6

Whenever a problem asks you to find the best possible translation (shift) to align two sets of points/marked cells, and you'd otherwise need to "try every shift and rescan everything," think: enumerate every pair of points (one from each set), compute the shift each pair implies, and tally votes for each distinct shift in a HashMap — the shift with the most votes is the answer, and this scales with the number of marked points, not the size of the full grid.

---

22. Interview Thinking

CODEBLOCK7

Applied here: the "aha" is realizing that a pair of matched points fully determines a specific shift — turning a "try every transformation" search into a "count how many pairs agree on each transformation" tally, a very reusable trick for alignment-style problems.

---

23. Mini Challenge

Try these before checking the answers:

1. Why does the shift implied by a pair INLINECODE293 have to be computed as INLINECODE294, and not, say, the midpoint or sum of the two points? 2. If INLINECODE295 has 5 ones and INLINECODE296 has 4 ones, what is the maximum possible number of INLINECODE297 pairs we'd need to consider, and why can't the final answer (the best overlap count) exceed the smaller of these two counts (4)? 3. Why is it safe to update INLINECODE298 incrementally, pair by pair, rather than waiting until the entire INLINECODE299 map is fully built before scanning it for the maximum?

Answer to Mini Challenge

1. A "shift" represents "how far and in what direction do I move a point to get from its old location to its new location" — that's precisely INLINECODE300. Since we're moving INLINECODE301's point INLINECODE302 to hopefully land on INLINECODE303's point INLINECODE304, the required shift is INLINECODE305. A midpoint or sum wouldn't represent "a translation amount" at all. 2. There are at most $5 \times 4 = 20$ pairs to consider. The final answer can never exceed $4$ (the smaller count) because the overlap count for any given shift can never be larger than the total number of INLINECODE306s in either* image individually — you can't have more matching pairs than the total number of INLINECODE307s available in the smaller image to match against. 3. Because INLINECODE308 is commutative and order-independent — updating INLINECODE309 immediately after processing each pair, versus waiting and scanning the whole completed map at the very end, both arrive at the exact same final maximum value; doing it incrementally just avoids a separate final pass over the map, saving a small amount of extra work.

---

24. Final Revision

🧠 Problem in One Sentence

Find the translation of one binary grid that maximizes the number of positions where both grids have a INLINECODE310.

🔑 Main Idea

Every pair of (a INLINECODE311 in img1, a INLINECODE312 in img2) implies exactly one shift that would align them; tally how many pairs imply each distinct shift, and the highest tally is the answer.

⚙️ Algorithm

1. Collect the INLINECODE313 positions of all INLINECODE314s in INLINECODE315 and in INLINECODE316. 2. For every pair INLINECODE317, compute the implied shift INLINECODE318. 3. Tally each distinct shift's vote count in a INLINECODE319 (using an encoded integer key). 4. Track and return the maximum tally seen across all pairs.

⏱️ Complexity

Time: $O(A \times B)$, where $A, B$ are the counts of INLINECODE320s in each image (worst case $O(n^4)$ for fully-dense images) Space: $O(n^2)$

🎯 Pattern to Remember

"Best translation/alignment between two point sets" $\rightarrow$ enumerate point pairs, tally the shift each pair implies, take the shift with the most votes — rather than testing every possible shift directly against the full grid.

---

25. Beginner Quiz

1. (Understanding) Why can we completely ignore all the INLINECODE321-cells in both images when solving this problem? 2. (Basic concept) What does the shift value INLINECODE322 represent, in plain words? 3. (Logic) Why does the number of votes a particular shift receives exactly equal the overlap count that shift would produce if actually applied to the whole image? 4. (Dry run) For INLINECODE323 and INLINECODE324, list the 1-positions in each, compute the implied shift(s), and determine the final answer. 5. (Complexity/pattern) Why does the voting approach's time complexity depend on the number of INLINECODE325s rather than the grid's total size, and in what scenario (sparse vs. dense images) does this actually provide a meaningful speed advantage over the brute-force approach?