Skip to content

835. Image Overlap

  • Time: $O(n^4)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
    constexpr int kMagic = 100;
    const int n = img1.size();
    int ans = 0;
    vector<pair<int, int>> ones1;
    vector<pair<int, int>> ones2;
    unordered_map<int, int> offsetCount;

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        if (img1[i][j] == 1)
          ones1.emplace_back(i, j);
        if (img2[i][j] == 1)
          ones2.emplace_back(i, j);
      }

    for (const auto& [ax, ay] : ones1)
      for (const auto& [bx, by] : ones2)
        ++offsetCount[(ax - bx) * kMagic + (ay - by)];

    for (const auto& [_, count] : offsetCount)
      ans = max(ans, count);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int largestOverlap(int[][] img1, int[][] img2) {
    final int kMagic = 100;
    final int n = img1.length;
    int ans = 0;
    List<int[]> ones1 = new ArrayList<>();
    List<int[]> ones2 = new ArrayList<>();
    Map<Integer, Integer> offsetCount = new HashMap<>();

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        if (img1[i][j] == 1)
          ones1.add(new int[] {i, j});
        if (img2[i][j] == 1)
          ones2.add(new int[] {i, j});
      }

    for (int[] a : ones1)
      for (int[] b : ones2) {
        final int key = (a[0] - b[0]) * kMagic + a[1] - b[1];
        offsetCount.merge(key, 1, Integer::sum);
      }

    for (final int count : offsetCount.values())
      ans = Math.max(ans, count);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
    kMagic = 100
    ones1 = [(i, j)
             for i, row in enumerate(img1)
             for j, num in enumerate(row)
             if num == 1]
    ones2 = [(i, j)
             for i, row in enumerate(img2)
             for j, num in enumerate(row)
             if num == 1]
    offsetCount = collections.Counter()

    for ax, ay in ones1:
      for bx, by in ones2:
        offsetCount[(ax - bx) * kMagic + (ay - by)] += 1

    return max(offsetCount.values()) if offsetCount else 0