The problem
Given an array of integers nums, return true if any value appears at least twice, and false if every value is different.
Examples
01
- Input
nums = [1, 2, 3, 1]
- Output
true
02
- Input
nums = [1, 2, 3, 4]
- Output
false
Constraints
- 1 ≤ nums.length ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
The idea
Comparing every pair of numbers takes n × n steps. Instead, remember what has gone past.
A hash set is a collection that answers “is this already in here?” in constant time on average. Walk the array: if the number is already in the set, it is a duplicate — stop. Otherwise add it. If the walk ends, every number was new.
- Time
- O(n) — each number is checked and added once
- Space
- O(n) — the set can hold every number
Solution
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: seen = set() for x in nums: if x in seen: return True seen.add(x) return False