Sponsored
Sponsored
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.
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.
1import java.util.*;
2
3public class ImageOverlap {
4 public static int largestOverlap(int[][] img1, int[][] img2) {
5 int n = img1.length;
6 int maxOverlap = 0;
7
8 for (int xShift = -n + 1; xShift < n; ++xShift) {
9 for (int yShift = -n + 1; yShift < n; ++yShift) {
10 maxOverlap = Math.max(maxOverlap, overlapCount(img1, img2, xShift, yShift));
11 }
12 }
13 return maxOverlap;
14 }
15
16 private static int overlapCount(int[][] img1, int[][] img2, int xShift, int yShift) {
17 int n = img1.length, count = 0;
18 for (int r = 0; r < n; ++r) {
19 for (int c = 0; c < n; ++c) {
20 if ((r + xShift >= 0 && r + xShift < n) && (c + yShift >= 0 && c + yShift < n)) {
21 count += img1[r][c] & img2[r + xShift][c + yShift];
22 }
23 }
24 }
25 return count;
26 }
27
28 public static void main(String[] args) {
29 int[][] img1 = {{1, 1, 0}, {0, 1, 0}, {0, 1, 0}};
30 int[][] img2 = {{0, 0, 0}, {0, 1, 1}, {0, 0, 1}};
31 System.out.println("Max Overlap: " + largestOverlap(img1, img2));
32 }
33}The Java solution involves the use of a largestOverlap function to traverse a range of shifts, computing the maximum overlap using overlapCount. The main method initializes examples and prints the result.
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.
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.
1using System.Collections.Generic;
public class ImageOverlap {
public static int LargestOverlapConvolution(int[,] img1, int[,] img2) {
int n = img1.GetLength(0);
var aOnes = new List<ValueTuple<int, int>>();
var bOnes = new List<ValueTuple<int, int>>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (img1[i, j] == 1) aOnes.Add((i, j));
if (img2[i, j] == 1) bOnes.Add((i, j));
}
}
var count = new Dictionary<string, int>();
int maxOverlap = 0;
foreach (var (ax, ay) in aOnes) {
foreach (var (bx, by) in bOnes) {
string shift = (ax - bx) + "," + (ay - by);
if (!count.ContainsKey(shift)) count[shift] = 0;
count[shift]++;
maxOverlap = Math.Max(maxOverlap, count[shift]);
}
}
return maxOverlap;
}
public static void Main() {
int[,] img1 = { { 1, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 } };
int[,] img2 = { { 0, 0, 0 }, { 0, 1, 1 }, { 0, 0, 1 } };
Console.WriteLine("Max Overlap Convolution: " + LargestOverlapConvolution(img1, img2));
}
}C# methodology applies value tuples to retain 1s positions, wherein a dictionary traces position overlaps. This ensures correct overlap tracking by differing translation strings.