A printing wheel carries n distinct labels, listed clockwise in wheel. Under the wheel sits a
ring of n slots, and slot j wants the label wanted[j].
Turning the wheel right by k (0 <= k < n) moves the label at index i to slot
(i + k) % n. A slot is matched when the label that lands on it equals wanted[j].
Return a list [k, matches]: the turn k with the most matched slots and that number of
matches. If several turns tie, choose the smallest k. For empty lists return [0, 0].
Examples
Input: wheel = [1, 2, 3, 4, 5], wanted = [4, 5, 1, 2, 9]
Output: [2, 4]
Explanation: turning right by 2 gives [4, 5, 1, 2, 3]; four slots match.
Input: wheel = [7, 8, 9], wanted = [1, 2, 3]
Output: [0, 0]
Explanation: no turn matches anything, so the smallest turn, 0, wins the tie.
Input: wheel = [1, 2, 3, 4], wanted = [2, 1, 4, 3]
Output: [1, 2]
Explanation: turns 1 ([4, 1, 2, 3]) and 3 ([2, 3, 4, 1]) both match 2 slots.
Constraints
0 <= len(wheel) == len(wanted) <= 10**5- The values in
wheelare distinct;wantedmay repeat values or hold values not on the wheel. -10**9 <= wheel[i], wanted[j] <= 10**9- Target: O(n) time. Trying every turn and comparing all slots is far too slow for the largest tests.
Goals
- Turn a search over all rotations into votes for a shift
- Use a dict from value to position to find each vote in O(1)
- Break ties on the smallest shift