Approach #1: Translate by Delta [Accepted]

Intuition and Algorithm

For each translation delta, we calculate the candidate answer overlap(delta), which is the size of the overlap if we shifted the matrix A by delta.

We only need to check delta for which some point in A maps to some point in B, since a candidate overlap must be at least 1. Using a Set seen, we remember if we've calculated overlap(delta), so that we don't perform this expensive check more than once per delta.

We use java.awt.Point (or complex in Python) to handle our 2D vectors gracefully. We could have also mapped a vector delta = (x, y) (which has coordinates between -(N-1) and N-1) to 2*N x + y for convenience. Note that we cannot map it to N*dx, dy as there would be interference: (0, N-1) and (1, -1) would map to the same point.

Complexity Analysis

  • Time Complexity: , where is the length of A or B.

  • Space Complexity: .


Approach #2: Count by Delta [Accepted]

Intuition and Algorithm

We can do the reverse of Approach #1: count every possible delta = b - a we see. If we see say, 5 of the same delta = b - a, then the translation by delta must have overlap 5.

Complexity Analysis

  • Time Complexity: , where is the length of A or B.

  • Space Complexity: .


Analysis written by: @awice.