⚡ TL;DR
3 ways to detect duplicate elements in a Python array — set-based, dictionary-based, and sorting approaches compared with complexity analysis.
Contains Duplicate (LeetCode #217) asks: “Does the array contain any value that appears at least twice?” It’s the simplest duplicate detection problem but still useful to master all three approaches.
Problem Statement
Given an integer array nums, return true if any value appears at least twice, otherwise return false.
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: trueApproach 1: Hash Set (Most Pythonic)
Use Python’s built-in set which automatically rejects duplicates by length.
def contains_duplicate_set(nums):
return len(nums) != len(set(nums))
# Test cases
print(contains_duplicate_set([1, 2, 3, 1])) # True
print(contains_duplicate_set([1, 2, 3, 4])) # False
print(contains_duplicate_set([])) # False (empty = no duplicates)Time Complexity: O(n) — hash lookup is O(1) average Space Complexity: O(n) — set stores all unique values in worst case
Why It Works
If len(set(nums)) != len(nums), some values must appear more than once. This works because set construction automatically throws away duplicates.
nums = [1, 2, 2, 3]
print(len(nums)) # 4
print(len(set(nums))) # 3 ([] -> {1, 2, 3})Approach 2: Dictionary / Counter
More explicit tracking with a dict or collections.Counter.
from collections import Counter
def contains_duplicate_counter(nums):
return any(v > 1 for v in Counter(nums).values())
# Or without Counter
def contains_duplicate_dict(nums):
seen = {}
for num in nums:
if num in seen:
return True
seen[num] = seen.get(num, 0) + 1
return FalseTime Complexity: O(n) Space Complexity: O(n)
Slightly more verbose but easier to extend if you need to know which values repeat or how many times.
Approach 3: Sorting (In-Place)
Sort the array, then check if any adjacent elements are equal.
def contains_duplicate_sort(nums):
nums.sort() # in-place sorting
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return FalseTime Complexity: O(n log n) — dominated by sorting Space Complexity: O(1) — sort is in-place
Why Sorting Isn’t the Default
Sorting is O(n log n), which is slower than O(n) hash-based approaches. But it uses O(1) space (vs O(n) for sets). If your array is already sorted by chance, or if the array is huge and memory-constrained, sorting can be the right call.
Comparison Table
| Approach | Time | Space | Readable | Recommended |
|---|---|---|---|---|
Set (len != len(set)) | O(n) | O(n) | ★★★★★ | ✅ Best for interviews |
| Dictionary / Counter | O(n) | O(n) | ★★★★☆ | ✅ Best if counting matters |
| Sorting | O(n log n) | O(1) | ★★★☆☆ | ⭐ Best when memory-bound |
Pythonic One-Liner Variations
# Minimal version
def contains_duplicate_v4(nums):
return len(set(nums)) < len(nums)
# Explicit loop version (easier to debug)
def contains_duplicate_v5(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
# Using list.count (slow — O(n²), avoid)
def contains_duplicate_v6_slow(nums):
return any(nums.count(x) > 1 for x in nums)Handling Numeric Edge Cases
Sets and dicts work fine with any hashable type, including:
# Works with floats
print(contains_duplicate_set([1.5, 2.5, 1.5])) # True
# Works with strings
print(contains_duplicate_set(["a", "b", "a"])) # True
# Works with booleans
print(contains_duplicate_set([True, False, True])) # TrueBut be careful with NaN:
import math
nums = [float('nan'), float('nan')]
# This returns False! Because NaN != NaN
print(contains_duplicate_set(nums)) # False
# Fix: use math.isnan for numeric arrays
def contains_duplicate_with_nan(nums):
for i, x in enumerate(nums):
for y in nums[i+1:]:
if x is y or (math.isnan(x) and math.isnan(y)):
return True
return FalseBenchmark: Which Is Fastest?
import timeit
def benchmark():
nums = list(range(10000)) + [9999] # 10001 elements, one duplicate
print("Set:", timeit.timeit(lambda: contains_duplicate_set(nums), number=100))
# Typically ~0.1s
print("Sort:", timeit.timeit(lambda: contains_duplicate_sort(nums.copy()), number=100))
# Typically ~0.4s (4x slower due to sort)
benchmark()The set approach is 2-4x faster than sorting for large arrays because O(n) beats O(n log n) as n grows.
Related Problems You Should Try Next
- Contains Duplicate II (#219) — same, but only within a sliding window of size
k - Contains Duplicate III (#220) — same but with absolute difference
- Find All Duplicates (#442) — find values that appear more than once, return list
Interview Follow-Up
A common follow-up: “Return the actual duplicate values, not just a boolean.”
def find_duplicates(nums):
seen = set()
duplicates = set()
for num in nums:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return list(duplicates)
print(find_duplicates([1, 2, 3, 1, 2])) # [1, 2]Master the set/len trick as your default answer: it’s readable, Pythonic, O(n) time, and shows you understand data structures. Use sorting only when constraints demand O(1) space.
