Introduction

What happens when one binary image is shifted over another and the goal is to find the position where the two images overlap the most?

That is exactly the idea behind LeetCode 835: Image Overlap.

Each image is represented as an n × n binary matrix containing only 0s and 1s. One image can be moved left, right, up, or down, but it cannot be rotated.

After every possible translation, the number of positions containing 1 in both images is calculated. The maximum value among all translations is the answer.

Since n is at most 30, a direct simulation of every possible translation is practical.

Question Link

LeetCode 835 – Image Overlap

Understanding the Problem

Consider two images:

and:

The first image can be translated.

For example, shifting Image 1:

can align several 1s from the two images.

The objective is to find the translation that produces the largest number of overlapping 1s.

Key Observation

A translation can be represented using two values:

For example:

means that a cell from Image 2 at:

is compared with Image 1 at:

The algorithm tries every possible row and column offset.

For an n × n matrix, each offset ranges from:

This covers every possible way the two images can overlap without requiring rotation.

Approach

The solution is divided into two parts.

Generate Every Translation

The largestOverlap() function generates every possible pair of row and column offsets.

handles vertical movement.

handles horizontal movement.

For every pair:

the helper function ch() calculates the overlap.

Count the Overlapping Ones

For every cell in img2, the translated position inside img1 is calculated:

The position is counted only when:

1. It is still inside img1.
2. img2[i][j] == 1.
3. img1[tarrow][tarcol] == 1.

Every such position contributes 1 to the overlap.

Java Solution

Visual Dry Run

Consider:

One useful translation is:

The idea is to move Image 2 relative to Image 1 and compare the positions containing 1.

How offset move on matrix?

The visual makes the important idea immediately clear: translation changes the positions being compared, while rotation is never performed.

How the Translation Works

Suppose:

For a cell in img2:

the corresponding position in img1 becomes:

For example:

is compared with:

If both contain 1, the overlap count increases.

The boundary check is important because some translations move cells outside the matrix.

For example, a large positive offset could produce:

In that case, the translated cell is outside the image and must not be counted.

Dry Run of the Helper Function

Suppose the translation is:

For every (i, j) in img2, the code calculates:

Then it checks:

and:

Only when both are true does the overlap increase.

Conceptually:

After checking every cell, ch() returns the overlap for that particular translation.

Exploring All Possible Translations

For a matrix of size n, the row offset is explored from:

to:

The same is done for the column offset.

For example, when:

the possible offsets are:

Therefore, all combinations are tested:

Each pair represents one possible translation.

The largest overlap among all of them becomes the final answer.

Why Boundary Checking Is Necessary

Imagine shifting an image to the right.

Some cells will move beyond the right edge of the matrix.

Those cells effectively disappear.

The same happens when moving:

1. left
2. up
3. down

Therefore, before accessing:

the solution verifies:

This prevents an ArrayIndexOutOfBoundsException and correctly handles pixels that move outside the image.

Why Rotation Is Not Needed

The problem allows only translation.

That means the relative structure of the 1s never changes.

For example:

can move:

but it cannot become:

through rotation.

This is why simply testing row and column offsets is enough.

Complexity Analysis

There are:

possible row offsets and the same number of column offsets.

Therefore, the number of translations is:

For every translation, the entire n × n matrix is scanned.

That takes:

So the overall complexity is:

which simplifies to:

Space Complexity

The solution uses only a few variables apart from the input matrices.

Therefore, the extra space is:

Why O(n⁴) Is Acceptable Here

At first glance, O(n⁴) may look expensive.

However, the constraint is:

This is a relatively small matrix.

The number of translations is at most:

and each translation checks at most:

cells.

So the total amount of work remains manageable.

This is a good example of an important DSA principle:

The best algorithm depends not only on the Big-O notation, but also on the actual constraints.

Interview Tip

When dealing with two matrices or grids and the problem allows one of them to move, a useful first question is:

Can the movement be represented using coordinates or offsets?

Here, every possible movement can be represented with:

Once that representation is identified, the problem becomes a straightforward simulation.

A good mental pattern is:

This pattern can also appear in problems involving:

1. Grid matching
2. Pattern alignment
3. 2D simulations
4. Image processing
5. Coordinate transformations

Conclusion

LeetCode 835 is a useful matrix simulation problem that demonstrates how a seemingly visual problem can be converted into simple coordinate calculations.

The main idea is to represent every possible translation using a row offset and column offset. For each translation, every cell of the second image is mapped to its corresponding position in the first image, and overlapping 1s are counted.

Because the matrix size is limited to 30 × 30, the O(n⁴) brute-force simulation is practical and keeps the implementation straightforward.

The most important takeaway is the coordinate-based way of thinking: when an object moves on a grid, represent that movement as an offset and systematically test the valid positions.