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 (N1)
and N1
) to 2*N x + y
for convenience. Note that we cannot map it to N*dx, dy
as there would be interference: (0, N1)
and (1, 1)
would map to the same point.
Complexity Analysis

Time Complexity: , where is the length of
A
orB
. 
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
orB
. 
Space Complexity: .
Analysis written by: @awice.