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].lengthn == img2.length == img2[i].length1 <= n <= 30img1[i][j] is either 0 or 1.img2[i][j] is either 0 or 1.This solution involves shifting one image over another in all possible positions and counting how many ones overlap. By varying the horizontal and vertical shifts, and calculating overlaps with respect to the position of img2, the solution finds the maximum overlap. This approach iterates over all possible translations, moving img1 relative to img2 and keeping track of the maximum overlap seen.
The C code defines two functions, overlapCount and largestOverlap. overlapCount calculates the number of overlapping 1s given a shift, while largestOverlap tries all possible x and y shifts, keeps track of the maximum overlap, and returns the result. The main function initializes the images and prints the maximum overlap.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^4), where n is the size of the matrix, due to the two nested loops and a cross-sectional overlap check for each.
Space Complexity: O(1), since the solution uses constant space apart from input storage.
This solution uses the concept of convolution by considering the images as arrays of points. We tallied the number of overlapping 1s for each relative translation using convolution properties without directly shifting arrays and used efficient matrix operations to compute overlaps.
The C convolution solution approaches the problem by varying the shift on rows and columns and utilizes cumulative positions of 1s. It identifies maximum overlap within those defined indices by focusing on particular shifts and computing resulting overlaps without directly shifting matrices.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^4), as it traverses through each overlap position and checks all cells.
Space Complexity: O(n), due to the allocation of cumulative arrays.
| Approach | Complexity |
|---|---|
| Brute Force Solution Using Translation | Time Complexity: O(n^4), where n is the size of the matrix, due to the two nested loops and a cross-sectional overlap check for each. Space Complexity: O(1), since the solution uses constant space apart from input storage. |
| Using Convolution | Time Complexity: O(n^4), as it traverses through each overlap position and checks all cells. Space Complexity: O(n), due to the allocation of cumulative arrays. |
image overlap | image overlap leetcode | leetcode 835 | matrix • Naresh Gupta • 8,792 views views
Watch 9 more video solutions →Practice Image Overlap with our built-in code editor and test cases.
Practice on FleetCode