Image Overlap LeetCode

This visual example lays the foundation for the concepts we'll explore further in the problem statement.

Problem statement

We are given two square binary matrices, Image A and Image B, of size $(n \times n)$ . Our task is to find the maximum overlap between them by shifting either Image A or Image B up, down, left, or right. The overlap is the count of positions where both matrices have a 1.

Some important points that need to be remembered while solving this problem:

We can slide either Image A or B, but not both, to find the maximum overlap.
The sliding operation doesn't involve rotating the images, only shifting them horizontally or vertically.
If a 1 in one of the images is shifted outside the matrix boundary during the sliding operation, it is considered erased and does not contribute to the overlap.
Image A and Image B have the same size, ( $n \times n$ ).

Our task is to determine the largest possible overlap that can be achieved between Image A and Image B under these constraints. The result should be an integer representing the maximum overlap. Now, let's map our previous example to the problem for better understanding.

Algorithm

Now that we’ve understood the problem, let’s understand it programmatically. The idea is to slide one matrix over the other and look for all possible overlaps in the up, down, left, and right directions. Educative 99 helps you solve complex coding problems like image overlap by teaching you to recognize patterns and apply the right algorithms.

Here’s how the algorithm works:

We start sliding Image A on the Image B in a loop.
1. We start with the index $[0][0]$ of the matrix.
2. Within this loop, we run a nested loop to check for the overlap in each iteration.
  1. In this nested loop, we count the ones in the current overlapped area.
  2. If the count of overlapping ones is greater than the previous counts, we update the maximum overlaps.

# count overlaps in arrays:
def find_max_overlap(row, col, A, B):
    # Initialize variables to store an overlap in different directions
    overlap_right_down = 0
    overlap_right_up = 0
    overlap_left_down = 0
    overlap_left_up = 0
    n = len(A)  # Assuming A and B are square matrices of size n x n
    for i in range(n):
        for j in range(n):
            # Calculate overlap in the right-down direction
            if i + row < n and j + col < n:
                overlap_right_down += A[i + row][j + col] & B[i][j]
            # Calculate overlap in the left-down direction
            if i - row >= 0 and j + col < n:
                overlap_left_down += A[i - row][j + col] & B[i][j]
            # Calculate overlap in the left-up direction
            if i - row >= 0 and j - col >= 0:
                overlap_left_up += A[i - row][j - col] & B[i][j]
            # Calculate overlap in the right-up direction
            if j - col >= 0 and i + row < n:
                overlap_right_up += A[i + row][j - col] & B[i][j]
    # Return the maximum overlap among the four directions
    return max(overlap_right_down, overlap_left_down, overlap_right_up, overlap_left_up)
def largestOverlap(A,B):
    max_overlap = 0
    # slides over the whole matrix in loops
    for i in range(len(A)):
        for j in range(len(A)):
            # calculate and update the maximum overlap in current iteration
            max_overlap = max(max_overlap, find_max_overlap(i, j, A, B))
    return max_overlap
# ---------------------------------------------------------------
A = [[0,0,0],
    [0,1,1],
    [0,0,0]]
B = [[0,0,0],
    [1,1,0],
    [0,1,0]]
print("The largest overlap is :",largestOverlap(A,B))

Code explanation

Line 2: The find_max_overlap function slides one position up, down, left, and right and finds the maximum number of 1’s overlapping in the given arrangement.
Lines 11–27: In the nested for loops, we iterate through the elements of matrices A and B to check for overlapping 1’s. We use four variables—overlap_right_down, overlap_right_up, overlap_left_down, and overlap_left_up—to keep track of the count of overlapping 1’s in different directions: right-down, right-up, left-down, and left-up.
Line 14: We calculate the overlap in the right-down direction by checking if we can move one matrix A down and to the right without going out of bounds. If so, we increment the count based on the overlapping values of A and B. (The same translations are performed for other directions in lines 18–27)
Line 30: The find_max_overlap function returns the maximum overlap among the four directions by finding the maximum value among overlap_right_down, overlap_left_down, overlap_right_up, and overlap_left_up.
Line 33: The largestOverlap function iterates over the entire matrix, considering different starting positions for A and B to calculate the maximum overlap in all possible arrangements. The maximum overlap is stored in the max_overlap variable and returned at the end.

Time complexity

The time complexity of the solution is $O(n^4)$ . where $n \times n$ represents the size of square matrices A and B. This is due to the presence of four nested loops, with two in the find_max_overlap function and two in the largestOverlap function. In each iteration of these loops, calculations depend on the size of the matrices, leading to a quartic time complexity concerning n.

Space complexity

The space complexity of the provided solution is constant, denoted as $O(1)$ . The algorithm uses a fixed amount of additional space for variables and loop counters, regardless of the size of the input matrices. It does not create any data structures proportional to the input size, resulting in a constant space complexity.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments