# 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>& A, vector>& B) { const int n = A.size(); const int magic = 100; int ans = 0; vector> onesA; vector> onesB; unordered_map 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& a : onesA) for (const pair& 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 onesA = new ArrayList<>(); List onesB = new ArrayList<>(); Map 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.merge(key, 1, Integer::sum); } 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 = collections.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