Image Overlap

Medium

Asked by:

14 views

Topics:

Arrays

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.

Example 1:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

The number of positions that have a 1 in both images is 3 (shown in red).

Example 2:

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

Example 3:

Input: img1 = [[0]], img2 = [[0]]
Output: 0

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the two images? Are they guaranteed to be square, or can they be rectangular?
Are the images represented as 2D arrays of 0s and 1s only, or can the pixel values be other numbers?
If there is no overlap between the two images (resulting in no common '1's after shifting), what value should I return?
Can the images be empty (i.e., have dimensions of 0x0)? If so, how should I handle that case?
Is one of the images guaranteed to be the same size or smaller than the other?

Brute Force Solution

Approach

Think of two partially transparent pictures stacked on top of each other. The brute force method involves sliding one picture across the other in every possible way, and counting how many parts line up perfectly. It's like physically moving one image and checking every single position.

Here's how the algorithm would work step-by-step:

Take the first picture and keep it still.
Now, take the second picture and place its top-left corner directly on top of the first picture's top-left corner. See how many pieces match.
Next, slide the second picture one spot to the right. Count the matching pieces again.
Keep sliding the second picture to the right, one spot at a time, all the way across the first picture, counting the matching pieces each time.
After you finish sliding the second picture to the right, move it down one spot and all the way to the left. Then, start sliding it to the right again, just like before, counting matching pieces.
Continue this process of moving the second picture down and across until you've covered every possible position where the second picture overlaps the first picture.
Remember the highest number of matching pieces you found in any of these positions. That's your answer.

Code Implementation

def image_overlap_brute_force(first_image, second_image):
    max_overlap_count = 0
    first_image_size = len(first_image)
    second_image_size = len(second_image)

    for row_offset in range(-second_image_size + 1, first_image_size):

        for column_offset in range(-second_image_size + 1, first_image_size):
            overlap_count = 0

            # Iterate through cells of the second image
            for second_image_row in range(second_image_size):
                for second_image_column in range(second_image_size):
                    first_image_row = second_image_row + row_offset
                    first_image_column = second_image_column + column_offset

                    # Ensure current cell is within bounds of the first image
                    if (0 <= first_image_row < first_image_size and
                            0 <= first_image_column < first_image_size):

                        # Count matching ones
                        if (first_image[first_image_row][first_image_column] == 1 and
                                second_image[second_image_row][second_image_column] == 1):
                            overlap_count += 1

            # Update the overall max value
            max_overlap_count = max(max_overlap_count, overlap_count)

    # Return the maximum overlap count
    return max_overlap_count

Big(O) Analysis

Time Complexity

O(n^4) – Let n be the dimension of the square images img1 and img2. The brute force approach iterates through all possible overlaps between the two images. We shift the second image both horizontally and vertically across the first image. The number of horizontal shifts ranges from -n+1 to n-1 (a total of 2n-1 shifts). Similarly, the vertical shifts also range from -n+1 to n-1 (2n-1 shifts). For each shift, we compare the overlapping elements, which takes O(n^2) time. Therefore, the overall time complexity is (2n-1) * (2n-1) * n^2, which simplifies to O(n^4).

Space Complexity

O(1) – The described brute force algorithm primarily iterates through the two input images without creating any significant auxiliary data structures. The number of matching pieces is tracked, and the highest count found is remembered, but these are stored in a few integer variables that consume constant space. The shifting and comparison of the second image only require a fixed number of variables to store offsets and counts, independent of the input image size. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The fastest way to solve this image overlap problem involves counting how many times a '1' in one image lands on top of a '1' in the other image for every possible way you can shift one image relative to the other. Instead of shifting the entire image, we only need to consider shifts where at least one '1' overlaps.

Here's how the algorithm would work step-by-step:

Find all the locations of '1's in both images. Think of them as coordinates.
For every coordinate in the first image, compare it to every coordinate in the second image.
Figure out the shift needed to align the coordinate in the first image with the coordinate in the second image. This is just the difference between their positions.
Keep track of how often each shift occurs. Each time a shift occurs, it means a '1' from the first image could overlap with a '1' from the second image using that shift.
The shift that occurs most often is the one that gives the maximum overlap. Count how many '1's overlap using that shift to get the answer.

Code Implementation

def image_overlap(image_one, image_two):
    image_one_ones = []
    image_two_ones = []
    
    for row_index in range(len(image_one)): 
        for col_index in range(len(image_one[0])):
            if image_one[row_index][col_index] == 1:
                image_one_ones.append((row_index, col_index))
            if image_two[row_index][col_index] == 1:
                image_two_ones.append((row_index, col_index))

    shift_counts = {}

    # Iterate through all pairs of ones to calculate shifts.
    for image_one_row, image_one_col in image_one_ones:
        for image_two_row, image_two_col in image_two_ones:
            row_shift = image_one_row - image_two_row
            col_shift = image_one_col - image_two_col
            
            if (row_shift, col_shift) in shift_counts:
                shift_counts[(row_shift, col_shift)] += 1
            else:
                shift_counts[(row_shift, col_shift)] = 1

    max_overlap = 0

    # Find the shift with the maximum overlap count.
    for shift in shift_counts:
        max_overlap = max(max_overlap, shift_counts[shift])

    return max_overlap

Big(O) Analysis

Time Complexity

O(n^4) – Let n be the dimension of the input images A and B. The first step is to find all coordinates of '1's in both images. In the worst case, all cells are '1's, resulting in O(n^2) coordinates for each image. The core of the algorithm involves comparing every coordinate from the first image's '1's to every coordinate from the second image's '1's. This results in O(n^2 * n^2) comparisons because each image could have O(n^2) '1's, leading to a nested loop structure. Each comparison calculates a shift and updates a counter, which takes constant time. Thus, the overall time complexity is O(n^4).

Space Complexity

O(N) – The space complexity is dominated by storing the coordinates of '1's in both images. Let N be the total number of cells in the input image. In the worst case, all cells in both images could be '1's. Thus, we would need to store O(N) coordinates for each image, and also O(N) to store shift counts in a hash map. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Image A or B is null or empty	Return 0, as no overlap is possible with an empty image.
Image A or B has dimensions of 1x1	Iterate through all possible shifts in the smaller image to count overlaps.
Image A and B are identical	The maximum possible overlap (size of image A) should be returned by shifting image B so it is on top of A (0, 0 shift).
Images A and B contain all zeros	The overlap count should return the size of Image A (or B), as every position will be overlapping 0s.
Images A and B are of vastly different sizes (e.g., one is 10x10, the other is 100x100)	The iteration should consider only the valid shift ranges, limiting the overall complexity.
Images A and B contain only 1s	The overlap count should return the minimum dimension size minus shifts when image B moves.
Integer overflow when calculating overlap sums (if not using boolean representation)	Use data types with sufficient range (e.g., long) to store the overlap sums, or use boolean addition (if data is binary).
No overlap exists between the images (all positions are misaligned)	The algorithm must return 0 in the case where no shift leads to any overlapping 1s.

Image A or B is null or empty

How to Handle:

Return 0, as no overlap is possible with an empty image.

Image A or B has dimensions of 1x1

How to Handle:

Iterate through all possible shifts in the smaller image to count overlaps.

Image A and B are identical

How to Handle:

The maximum possible overlap (size of image A) should be returned by shifting image B so it is on top of A (0, 0 shift).

Images A and B contain all zeros

How to Handle:

The overlap count should return the size of Image A (or B), as every position will be overlapping 0s.

Images A and B are of vastly different sizes (e.g., one is 10x10, the other is 100x100)

How to Handle:

The iteration should consider only the valid shift ranges, limiting the overall complexity.

Images A and B contain only 1s

How to Handle:

The overlap count should return the minimum dimension size minus shifts when image B moves.

Integer overflow when calculating overlap sums (if not using boolean representation)

How to Handle:

Use data types with sufficient range (e.g., long) to store the overlap sums, or use boolean addition (if data is binary).

No overlap exists between the images (all positions are misaligned)

How to Handle:

The algorithm must return 0 in the case where no shift leads to any overlapping 1s.