Image Overlap - Practice Coding Problems

Image Overlap - Problem

Array Matrix Medium

You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.

We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.

Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.

Return the largest possible overlap.

Input & Output

Example 1 — Basic Translation

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

› Output: 3

💡 Note: We translate img1 to the right by 1 unit. After translation: img1[0][1] aligns with img2[0][1], img1[1][1] aligns with img2[1][1], and img1[2][1] aligns with img2[2][1]. Total overlap is 3.

Example 2 — No Translation Needed

$ Input: img1 = [[1]], img2 = [[1]]

› Output: 1

💡 Note: Both images have a single 1 at position (0,0). No translation needed, overlap is 1.

Example 3 — No Overlap Possible

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

› Output: 0

💡 Note: img1 has no 1s, so regardless of translation, there can be no overlap with img2's 1s.

Constraints

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 ≤ n ≤ 30
img1[i][j] is either 0 or 1
img2[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Images

Two binary matrices with 1s at different positions

Slide & Count

Try different translations and count overlapping 1s

Maximum Overlap

Return the highest overlap count found

Key Takeaway

🎯 Key Insight: Only positions with 1s matter for overlap calculation

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is that we only need to consider positions where 1s exist, not empty positions. We can either try all possible translations (brute force) or focus on 1s coordinates to reduce constant factors. Best approach uses coordinate mapping: Time: O(n⁴), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Translations	O(n⁴)	O(1)	Try every possible translation offset and count overlapping 1s
Focus on 1s Only	O(n⁴)	O(n²)	Only consider positions with 1s to reduce unnecessary calculations

Try All Translations — Algorithm Steps

Step 1: Iterate through all possible translation offsets dx and dy
Step 2: For each offset, shift img1 and count overlapping 1s with img2
Step 3: Keep track of the maximum overlap found

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Position

Start with both images in original positions

Try Translation

Slide img1 by offset (dx, dy) and count overlaps

Find Maximum

Keep track of the best overlap found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** img1, int** img2, int n) {
    int maxOverlap = 0;
    
    // Try all possible translations
    for (int dx = -(n-1); dx < n; dx++) {
        for (int dy = -(n-1); dy < n; dy++) {
            int overlap = 0;
            // Check overlap for this translation
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // Position in img1 after translation
                    int ni = i + dx, nj = j + dy;
                    // Check if translated position is within bounds
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                        if (img1[i][j] == 1 && img2[ni][nj] == 1) {
                            overlap++;
                        }
                    }
                }
            }
            if (overlap > maxOverlap) {
                maxOverlap = overlap;
            }
        }
    }
    
    return maxOverlap;
}

int** parseMatrix(char* line, int* n) {
    // Simple parsing for [[1,0],[0,1]] format
    *n = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0) (*n)++;
    }
    
    int** matrix = (int**)malloc(*n * sizeof(int*));
    for (int i = 0; i < *n; i++) {
        matrix[i] = (int*)malloc(*n * sizeof(int));
    }
    
    // Parse matrix values
    int row = 0, col = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] >= '0' && line[i] <= '1') {
            matrix[row][col++] = line[i] - '0';
            if (col == *n) {
                row++;
                col = 0;
            }
        }
    }
    
    return matrix;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int n1, n2;
    int** img1 = parseMatrix(line1, &n1);
    int** img2 = parseMatrix(line2, &n2);
    
    int result = solution(img1, img2, n1);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < n1; i++) {
        free(img1[i]);
        free(img2[i]);
    }
    free(img1);
    free(img2);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Two nested loops for translation offsets O(n²), and for each offset, two nested loops to check the matrix O(n²)

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to store counters and maximum

✓ Linear Space

58.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Translations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler