Skip to content

835. Image Overlap

  • Time: $O(n^2)$
  • 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>>& A, vector<vector<int>>& B) {
    const int n = A.size();
    const int magic = 100;
    int ans = 0;
    vector<pair<int, int>> onesA;
    vector<pair<int, int>> onesB;
    unordered_map<int, int> map;

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        if (A[i][j] == 1)
          onesA.emplace_back(i, j);
        if (B[i][j] == 1)
          onesB.emplace_back(i, j);
      }

    for (const pair<int, int>& a : onesA)
      for (const pair<int, int>& b : onesB)
        ++map[(a.first - b.first) * magic + (a.second - b.second)];

    for (const auto& [_, value] : map)
      ans = max(ans, value);

    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[][] A, int[][] B) {
    final int n = A.length;
    final int magic = 100;
    int ans = 0;
    List<int[]> onesA = new ArrayList<>();
    List<int[]> onesB = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        if (A[i][j] == 1)
          onesA.add(new int[] {i, j});
        if (B[i][j] == 1)
          onesB.add(new int[] {i, j});
      }

    for (int[] a : onesA)
      for (int[] b : onesB) {
        final int key = (a[0] - b[0]) * magic + a[1] - b[1];
        map.put(key, map.getOrDefault(key, 0) + 1);
      }

    for (final int value : map.values())
      ans = Math.max(ans, value);

    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
    n = len(A)
    magic = 100
    onesA = []
    onesB = []
    dict = defaultdict(int)

    for i in range(n):
      for j in range(n):
        if A[i][j] == 1:
          onesA.append([i, j])
        if B[i][j] == 1:
          onesB.append([i, j])

    for a in onesA:
      for b in onesB:
        dict[(a[0] - b[0]) * magic + (a[1] - b[1])] += 1

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