You are given a list of whole numbers called nums. Return true if any value appears in the list at least twice. Return false if every value appears exactly once.
The list can hold up to 100,000 numbers. Each number is between -10^9 and 10^9, read "minus ten to the power nine and ten to the power nine", which is minus one billion to one billion.
For each number, you are really asking one question: "have I already seen this value earlier in the list?" If the answer is ever yes, you can stop and return true. If you reach the end and the answer was always no, return false.
So the whole problem comes down to answering "have I seen this before?" quickly. The rest of the page is about making that one question cheap.
The most direct idea compares every number with every number after it.
python
def containsDuplicate(nums): n = len(nums) for i in range(n): # pick one number for j in range(i + 1, n): # compare it with every later number if nums[i] == nums[j]: return True return False
This is correct. But look at what the inner loop does. For the number at position i, it walks the rest of the list looking for one value. It is a search. And it repeats that search from scratch for every i, forgetting everything it learned last time.
For 100,000 numbers, the two loops make about \frac{n^2}{2} comparisons. That is \frac{100{,}000 \times 100{,}000}{2} = 5{,}000{,}000{,}000, five billion comparisons. A judge usually allows around a hundred million simple steps per second, so this takes close to a minute and fails.
The waste in one sentence: every pass of the inner loop searches the list again for a value we could have simply remembered.
Keep a memory of every value you have walked past. Then "have I seen this?" becomes a lookup in that memory instead of a search through the list.
The right memory is a hash set. A set is a collection that holds each value at most once. A hash set is a set that finds a value without looking through all of them. It turns the value into a number, called its hash, and uses that number to jump straight to the spot where the value would be stored. So asking "is 7 in the set?" takes about the same time whether the set holds ten values or ten million. The details of that jump are in 4.3.
So the plan is:
Start with an empty set.
Walk the list once, from left to right.
For each number, ask the set whether it already holds that number.
If yes, you found a duplicate. Return true.
If no, add the number to the set and move on.
If the walk ends with no duplicate found, return false.
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: seen = set() # (1) for n in nums: # (2) if n in seen: # (3) return True # (4) seen.add(n) # (5) return False # (6)
ts
function containsDuplicate(nums: number[]): boolean { const seen = new Set<number>(); // (1) for (const n of nums) { // (2) if (seen.has(n)) { // (3) return true; // (4) } seen.add(n); // (5) } return false; // (6)}
(1) seen = set(). We create an empty set. Its job is to remember every value we have already walked past. It starts empty because, before the walk begins, we have seen nothing.
(2) for n in nums. We visit the numbers one at a time, left to right. The name n holds the current number. We never go back, so each number is visited exactly once.
(3) if n in seen. This is the question from the top of the page: "have I already seen this value?" The in operator on a set does a hash lookup, so it does not scan the set. In TypeScript the same question is seen.has(n).
(4) return True. If the set already holds n, then n appeared earlier in the list and is appearing again now. That is a duplicate. We return straight away. There is no reason to look at the rest of the list, because one duplicate is enough to answer true. This early exit is a real saving on inputs where the repeat comes near the start.
(5) seen.add(n). The number was new. We add it to the set so that a later copy of it will be caught at line (3).
(6) return False. We reach this line only if the loop finished without ever returning. That means every number was new when we met it, so no value appears twice.
Lines (3) and (5) must stay in that order. Suppose you swapped them, and added n first and then asked whether n is in the set. The answer would always be yes, because you just put it there. The very first number would be reported as a duplicate of itself, and every input would return true.
So the rule is: ask first, then remember. An element must never be allowed to match itself. You will see this exact rule again in 4.4.3 Two Sum, for the same reason.
Time. The loop runs once for each of the n numbers. Inside one turn, we do at most one lookup and one insert. A hash-set lookup and a hash-set insert each take a small fixed amount of work on average, which we write as O(1), read "order one" and meaning "constant, not growing with n". So the total work is n turns times a constant, which is O(n), read "order n".
Space. In the worst case there is no duplicate. Then every number gets added, and the set ends up holding all n of them. So the extra memory is O(n).
We have traded memory for time. The brute force used no extra memory but took O(n^2) time. This version uses O(n) memory and takes O(n) time.
On average, yes. The word to use is expectedO(1). If someone chose the input on purpose so that every value landed in the same spot of the set, each lookup would have to look through all of them, and the whole thing would slow to O(n^2). Real languages protect against this by mixing a random number into the hash each time the program starts, so an attacker cannot predict where values will land (4.3).
Sort first, then compare neighbours. After sorting, equal values sit next to each other. So one pass that compares nums[i] with nums[i - 1] finds any duplicate.
python
nums.sort() # equal values are now side by sidefor i in range(1, len(nums)): if nums[i] == nums[i - 1]: return Truereturn False
Sorting takes O(n \log n) time, read "n log n", which grows a little faster than n. It needs no set, so the extra memory is O(1) (ignoring the memory the sort itself uses). Use this when memory is tight and you are allowed to change the order of the caller's list.
Compare sizes.len(set(nums)) != len(nums) is one line and correct. A set drops repeated values, so if any value repeated, the set is smaller than the list. The cost is that it builds the whole set before it can answer, so it loses the early exit from line (4).
Contains Duplicate II. The two equal values must also be at most k positions apart. Keep a set of only the last k values. When the window moves past a value, remove it from the set. This is the sliding window from 4.6.
Values limited to 1 to n. You do not need a hash at all. Make a list of n + 1 booleans and use the value itself as the position: seen_flag[value] = True. A small, known range of values turns a hash into a plain list index. The same idea returns in 4.4.5.
Find the Duplicate Number. Exactly one value repeats and you may use no extra memory and may not change the list. Both answers on this page are ruled out, which forces a clever trick with two pointers. That is 4.9.8.
Too many values to fit in memory. A Bloom filter is a set that uses far less memory but sometimes says "seen" for a value it never saw. It never says "not seen" for a value it did see. 4.29 explains it.
The general lesson: when the inner loop of a brute force is asking "have I seen this?", replace that loop with a set.
"Can you do it without extra memory?" They are checking whether you know the trade-off. A clear reply is: "Yes, by sorting first. That costs O(n \log n) time and changes the caller's list. Am I allowed to change it?" Asking that question is part of the answer. The weak answer jumps straight to sorting without noticing it changes the input.
"Is the set lookup O(1)?" They want the word expected, and the reason it can fail. Most candidates say "yes" and stop.
"What if you add before you check?" They are checking that you understand why the order matters, not just that you copied it. Every input would return true, because each number would match itself.
"What if the values are between 1 and n?" Replace the set with a boolean list indexed by value. No hashing at all.
One thing to volunteer: say that the early return means the best case is very fast. If the duplicate sits in the first two positions, the function returns after two steps, while the one-line len(set(nums)) version always does all n steps.
Next:4.4.2 Valid Anagram. The same hashing idea, but now we need to know how many of each value, not only whether we saw it.