Problem overview
The method firstRepeat(nums) reads an array of integers from left to right and returns the first value that appears for the second time. If no value appears twice, it returns -1.
For [3, 1, 4, 1, 3] the answer is 1. Reading from the left you see 3, 1, 4 and then 1 again. The second 1 (index 3) arrives before the second 3 (index 4), so 1 is the answer, even though 3 appeared first. For [2, 7, 9] nothing repeats and the answer is -1. For [6, 6, 6, 6] it is 6, since the second 6 at index 1 is already a repeat.
Approach
The question "have I seen this number before?" is what a set answers quickly. Keep a set of the numbers read so far. For each new number, check the set first. If the number is in it, it is a repeat, and because you read in order, it is the earliest one. If not, add it and move on.
The order of the two actions matters. Check first, then add. If you added the number before checking, every number would find itself in the set and the function would return the first element every time.
Comparing every pair of elements with two nested loops would also find the answer but would take time proportional to the square of the array length. The set does it in one pass.
Step by step
- Create an empty set named
seenwithnew Set(). - Loop over
numswithfor...of, from left to right. - Check membership: if
seen.has(num), returnnum. This is the first value to repeat. - Remember the number with
seen.add(num), below the check. - Return -1 after the loop. Reaching the end means nothing was repeated.
The solution in JavaScript
class Solution {
firstRepeat(nums) {
let seen = new Set();
for (let num of nums) {
if (seen.has(num)) {
return num;
}
seen.add(num);
}
return -1;
}
}
On the JavaScript side, a Set has has to test membership and add to insert, and both are fast. A return inside the loop ends the whole function at once, so there is no need for a flag or a break. The loop uses let num; const would work as well, since num is not reassigned.
Using -1 as the "nothing found" value is safe only because the lesson guarantees that every number is zero or more, so -1 can never be a real answer. If negative numbers were allowed, you would need a different signal, such as null.
Tracing the example
For [3, 1, 4, 1, 3], seen starts empty. The 3 is not in it and is added. The 1 is not in it and is added. The 4 is added. The second 1 is already there, so the function returns 1 at index 3. The final 3 is never reached. For [2, 7, 9], each number is new and added, the loop ends, and the function returns -1.
Complexity
Time: O(n). The loop visits each element at most once, and has and add take constant time on average. The function can also stop early when a repeat appears.
Space: O(n) in the worst case. When no value repeats, the set ends up holding all the numbers.
Edge cases and common mistakes
- Adding before checking. The function would return the first number in every array.
- Returning the first value that has a duplicate. That is a different question. In
[3, 1, 4, 1, 3]it would be 3, but the task asks for the value whose second appearance comes first, which is 1. - Forgetting the final
return -1. Without it the function returnsundefinedwhen nothing repeats. - Using
seen.includes.includesbelongs to arrays, so aSethas no such method and the call throws aTypeError. Usehas. - A single number.
[5]gives -1, since nothing can repeat.
Testing
[3, 1, 4, 1, 3]gives1.[2, 7, 9]gives-1.[6, 6, 6, 6]gives6.[5]gives-1.
