Contains Duplicate
The key idea
Track the values you have already seen in a hash set. The first time a value reappears you can answer immediately, turning a quadratic all-pairs comparison into a single linear pass.
Problem
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
The order of the elements does not matter; you only need to decide whether at least one value is repeated anywhere in nums.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Examples
Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM