Abstract / Summary

Given two binary images, find the maximum number of overlapping 1s when one image is translated over the other.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 64% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation determines the maximum number of overlapping 1-pixels when one binary image is shifted over another. It treats the problem as a search for the translation vector that aligns the greatest number of foreground pixels between the two matrices. The algorithm proceeds in three logical phases: extracting the positions of foreground pixels from the second image, enumerating all possible translation vectors generated by pairing foreground pixels from the first image with those from the second, and finally selecting the translation that occurs most frequently.

Extraction of Ones from the Second Image

To avoid repeatedly scanning the entire second matrix during the inner loop, the code first builds a compact list containing the coordinates of every 1 in img2. This one-time pass reduces the work of the later nested loops to a simple iteration over a pre-computed collection.

ones = []
for y in range(height):
    for x in range(width):
        if img2[y][x] == 1:
            ones.append((x, y))

The resulting ones list holds tuples (x, y) that represent the exact locations of foreground pixels in the second image.

Motion Vector Counting

The core of the algorithm iterates over every 1 in the first image and, for each such pixel, pairs it with every entry in the ones list. The difference between the coordinates yields a translation vector (vx, vy). Rather than storing these vectors in a hash map, the implementation maps each possible vector to a unique index in a flat integer array called motion. The size of this array is width * height * 4, which covers the full range of horizontal and vertical offsets from -width to +width and -height to +height. The index calculation adds the width and height offsets to shift negative values into the non-negative index space.

motion = [0] * (width * height * 4)

for y in range(height):
    for x in range(width):
        if img1[y][x] == 1:
            for x2, y2 in ones:
                vx = x2 - x
                vy = y2 - y
                id = (vx + width) + (vy + height) * 2 * width
                motion[id] += 1

Each increment of motion[id] records that a particular translation aligns another pair of foreground pixels. By the end of the nested loops, the array entry with the highest count corresponds to the translation that produces the largest overlap.

Final Result Computation

After all vectors have been tallied, the algorithm extracts the maximum count from the motion array, which directly represents the size of the best possible overlap.

return max(motion)

If no overlapping 1s exist for any translation, the array remains filled with zeros and the function correctly returns 0.

Edge Cases Handled

The code gracefully handles images that contain no foreground pixels. In such a scenario, the ones list is empty, the inner loop never executes, and the motion array stays at its initial zeroed state, leading to a return value of 0. When both images are completely filled with 1s, every possible translation is counted, and the maximum entry reflects the full image size, because the translation vector (0, 0) aligns all pixels. The indexing scheme also accommodates negative translation components by offsetting them with width and height, ensuring that vectors that would otherwise map to negative indices are safely stored within the bounds of the flat array. Additionally, the algorithm does not assume any particular relationship between the dimensions of the two images beyond them being equal; the loops iterate over the shared height and width, so mismatched dimensions would simply result in the smaller common area being processed.

Performance Optimizations

A notable optimization is the pre-extraction of 1 positions from the second image, which reduces the inner loop to a simple iteration over a list rather than a full matrix scan. This change cuts the number of element accesses dramatically when img2 contains relatively few foreground pixels.

The use of a one-dimensional integer array for counting motion vectors eliminates the overhead of hash-based structures. Direct indexing with arithmetic that incorporates the image dimensions provides constant-time updates and leverages contiguous memory layout for cache friendliness.

By calculating the unique identifier id with a single arithmetic expression, the code avoids conditional branches inside the innermost loop, further streamlining execution.

Finally, the final max call operates on a flat list of primitive integers, which is highly optimized in the underlying runtime, allowing the result to be obtained with minimal additional work.

Imagine there are two large square grids filled with little squares, and some of those squares are colored in like tiny stars. This code wants to see how well those star patterns can be lined up if one grid slides over the other.

First, the computer looks at the second grid and makes a list of exactly where all the stars are hiding. This helps the computer remember where they are so it does not have to search the whole grid every single time.

Next, the computer looks at the first grid to find all of its stars. For every star in the first grid, it looks at the list of stars from the second grid and figures out how far it would need to slide to make them land on top of each other. It keeps track of these distances using a special long list that acts like a scoreboard.

Every time a specific slide distance makes two stars land in the same spot, the computer adds a point to that specific spot on the scoreboard. When the computer finish checking all the stars, it looks at the scoreboard to see which slide distance got the most points. The spot with the highest number tells the biggest overlap possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java				Go	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality