First Repeating Element asks you to find the element that repeats earliest in an array. It is a clean drill on the most useful warm-up trick in the field: using a set to remember what you have already seen, and choosing your scan direction to make the answer fall out for free.
Problem. Given an array of integers nums, return the index of the first element that appears
more than once (the smallest index whose value is repeated somewhere in the array). If no element
repeats, return -1.
Example: nums = [1, 5, 3, 4, 3, 5, 6] → answer 1. The value 5 (at index 1) is the first element
that shows up again later. The value 3 also repeats, but it first appears at index 2, which is later.
The slow way first
The obvious idea: for each element, scan the rest of the array to see if it appears again. The first element that does is the answer. That works, but it is O(n²) — for a large array those nested scans are far too slow.
The question to ask: while I am looking at one element, what do I wish I already knew? I wish I knew whether this value shows up anywhere else. A set answers that in O(1) — and the direction I scan in lets me pin down the first such index without any extra bookkeeping.
The idea: scan right to left into a set
Walk the array from right to left. Keep a seen set. For each value, before adding it, check: is this value already in seen? If yes, it repeats — so record its index in ans. Then add the value to the set and keep going.
The key insight: because we move right to left, every time we overwrite ans we are at a smaller index than before. So after the full pass, ans holds the smallest index of any repeated value — exactly the first repeating element.
Walk through it
Step through the animation. The pointer i starts at the right end and moves left. The seen set fills up underneath. The first four values (6, 5, 3, 4) are all new. At index 2 the value 3 is already in the set, so ans becomes 2. At index 1 the value 5 is also already in the set, so ans updates to the smaller index 1. Index 0 is new, the scan ends, and we return ans = 1.
Pseudocode
make an empty set called "seen"
ans = -1
for i from last index down to 0:
if nums[i] is in seen:
ans = i # repeat found; smaller index overwrites
add nums[i] to seen
return ans # smallest repeating index, or -1The Python solution
def first_repeating(nums):
seen = set()
ans = -1
for i in range(len(nums) - 1, -1, -1):
if nums[i] in seen:
ans = i
seen.add(nums[i])
return ansseenis a set of the values we have encountered so far (we only need the values, not their indices).ansstarts at-1, the answer when nothing repeats.range(len(nums) - 1, -1, -1)walks the indices backwards, from the last element down to index 0.- Line 5 is the O(1) lookup —
nums[i] in seenchecks the set, not the whole array. - Line 6 overwrites
anson every repeat. Since we go right to left, the last write wins and it is always the smallest index seen.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (rescan for each) | O(n²) (slow) | nested scans |
| Set, one pass (this solution) | O(n) (moderate) | one pass, O(1) lookups |
O(n) (moderate)We trade O(n) extra space (the set) for a big speed win: O(n²) becomes O(n). That trade — use a set to remember things and look them up instantly — shows up in a huge number of array problems.
When this pattern shows up
Any time a problem asks "has this value appeared before / is there a duplicate / which one repeats," reach for a set. The extra lever here is scan direction: scanning right to left lets the smallest repeating index fall out naturally, with no comparison of indices needed.
Do not confuse the first repeating element with the first element whose second occurrence comes
earliest. Here we want the smallest index of any value that appears more than once. Scanning right to
left and overwriting ans guarantees we keep the smallest such index.
Practice
For nums = [1, 5, 3, 4, 3, 5, 6] scanned right to left, ans becomes 2 at index 2 (value 3). What happens at index 1?
1. Why scan right to left instead of left to right?
2. What does the set store?
3. What should the function return when no element repeats?
4. What is the extra space used by this solution?