Does any number show up twice? Walk the list once with a set of values you've already seen, and stop the moment one repeats.
▼The problem
LeetCode 217 (Easy). Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
Examples (the LeetCode ones): [1, 2, 3, 1] → **true** (1 appears twice); [1, 2, 3, 4] → **false**.
The solution
def containsDuplicate(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return FalseTranscript
Contains Duplicate. Given an array of numbers, return true if any value appears at least twice, and false if every value is distinct.
Take one, two, three, one. The one appears twice, so the answer is true. But one, two, three, four are all different: false.
The naive way compares every pair, about n squared checks. Sorting first and comparing neighbors is better, n log n. But we can do better.
The key idea: keep a set of the values you've seen. A set answers "have I seen this?" in constant time. Check each number: if it's in the set, stop. Otherwise, add it.
In code, start with an empty set. For each number, if it's already in the set, return true. Otherwise, add it. If the loop ends, return false.
Let's run one, two, three, one. One is new, so it's stamped into the set. Two is new. Three is new. Then one again: it's already there. Duplicate! Return true, right away. With one, two, three, four, every number is new, and we return false.
Each number is checked once, so the time is O of n. The set can hold up to n values, so the space is O of n too.
Remember what you've seen, and stop at the first repeat. That's Contains Duplicate.