Problem overview
The method removeRepeats receives a list of integers nums and returns a new list in which each value appears once. The first copy of every value stays, later copies are dropped, and the values keep the order in which they first appear.
For [3, 1, 3, 2, 1] the result is [3, 1, 2]: the second 3 and the second 1 are repeats. For [6, 6, 6, 6] the result is [6], and for [4, 9, 2], which has no repeats, the list comes back unchanged.
Approach
Read the numbers from left to right. For each one, ask: have I met this value before? If not, it is a first copy, so it goes into the result. If so, skip it.
"Have I met it before?" needs a memory of the values seen so far. A set is the right memory: num in seen is fast, and adding a value twice is harmless. A second collection, a list, holds the answer, because a set cannot keep the order.
That split is the heart of the lesson: the set answers the question, the list keeps the order. Turning the input into a set with set(nums) would drop the repeats too, but a set makes no promise about order, so the result could come out in a different order than the one the task demands. For the input [40, 3, 17, 3], list(set(nums)) gives [40, 17, 3].
Step by step
- Create the empty set
seen = set(). - Create the empty list
result = []. - Loop with
for num in nums. Reading left to right matters: the first copy is the one to keep. - Inside the loop, test
num not in seen, which is true only for a first copy. - When it is, append
numtoresult. - Also add
numtoseen, so the next copy is recognised as a repeat. - After the loop, return
result.
The solution in Python
class Solution:
def removeRepeats(self, nums: List[int]) -> List[int]:
seen = set()
result = []
for num in nums:
if num not in seen:
result.append(num)
seen.add(num)
return resultNotes on the details:
seen = set()and not{}: empty braces make a dictionary.- The method returns a new list.
numsitself is not changed. - The return is after the loop. Inside the loop it would hand back only the first value.
Another way
Dictionaries remember the order in which keys were added, and dict.fromkeys makes a key for each value once, so list(dict.fromkeys(nums)) also keeps the first copies in order. For [3, 1, 3, 2, 1] it gives [3, 1, 2]. The loop above shows the idea more openly, which is why the lesson writes it out.
Edge cases
A list with one number returns that number. Negative numbers and zero need no special care, since the set treats them like any other value. The task guarantees at least one number; an empty list would simply give an empty result.
Testing
| nums | result |
|---|---|
[3, 1, 3, 2, 1] | [3, 1, 2] |
[6, 6, 6, 6] | [6] |
[4, 9, 2] | [4, 9, 2] |
Common mistakes
- Returning
list(set(nums)). The repeats go away, but the order is not guaranteed to survive. - Forgetting to add to
seen. Then nothing is ever recognised as a repeat and the list comes back unchanged. - Checking the result list instead of a set.
num not in resultworks, but looks through the list value by value each time.
