Closest Repeat Distance
Problem
You are given a list of values. Among all pairs of positions that hold the same value, find the pair that sits closest together and return the gap between them, measured as the difference of their indexes. If no value appears twice, return -1.
Examples
Input: values = [7, 1, 3, 7, 1, 7]
Output: 2
Why: the 7s at indexes 3 and 5 are two apart; the 1s are three apartInput: values = [3, 8, 8, 3]
Output: 1
Why: the two 8s sit side by sideInput: values = [5, 6, 7]
Output: -1
Why: edge case, nothing repeatsHints
0 / 3
Comparing every pair of positions works, but the work grows with the square of the length: double the list and it takes four times as long.
For the value at the current position, only one earlier position can give the smallest gap. Which one is it, and what would let you find it instantly?
Walk the list once, keeping a map from each value to the last index where you saw it. When the current value is already in the map, compare the current index minus the stored one with the best gap so far, then overwrite the stored index.
Solution
The closest earlier twin of any position is the most recent one, so remembering only the last index of each value is enough. A hash map answers that lookup in constant time on average, which turns the quadratic pair check into a single pass. The map is updated after every step, so it always holds the latest index of each value. Time is O(n) on average, and space is O(n) for the map.
def closest_repeat(values):
last_seen = {} # value -> most recent index
best = -1
for i, v in enumerate(values):
if v in last_seen:
gap = i - last_seen[v]
if best == -1 or gap < best:
best = gap
last_seen[v] = i # only the latest index can matter later
return best
print(closest_repeat([7, 1, 3, 7, 1, 7])) # -> 2
print(closest_repeat([3, 8, 8, 3])) # -> 1
print(closest_repeat([5, 6, 7])) # -> -1Stuck on the idea rather than the code? What Is Big-O? covers it.