Remember where you first saw it
Keep the first position of every value in a map. About 8 minutes.
A notebook of first sightings
Birdwatchers keep a log: the first time they spot each kind of bird, they note the date. Later, when they see that bird again, they can say how long it's been since the first sighting.
A map works as that log. The key is a number from the array, and the value is the box where you first saw it. When you meet a number that's already in the log, the gap back to its first sighting is how far apart the two copies are.
3 is new: note that it was first seen in box 0.
Never overwrite the first sighting
You want the pair of equal values that's as far apart as possible. For any later copy, the copy furthest to the left gives the biggest gap. So once a number is in the log, leave its entry alone.
Updating it to the latest sighting would shrink every gap you measure afterwards. The answer for 3, 1, 4, 1, 5, 3 is 5, the two 3s at the ends.
first = {}
best = 0
for j, x in enumerate(nums):
if x in first:
best = max(best, j - first[x])
else:
first[x] = j
return bestIn 2, 7, 2, 2, the walk reaches the last 2 (box 3). What gap does it measure?
- A3
- B1
- C2
Show the answer
3. The log still says the first 2 was in box 0, so the gap is 3.
Widest equal pair
You get a list of numbers. Find two positions i < j holding the same value, as far apart as possible, and return j − i. If no value appears twice, return 0.
nums = [3, 1, 4, 1, 5, 3] → 5
0 ≤ n ≤ 1,000,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000