Contains Duplicate Solution

Problem

Given an integer array, determine whether any value appears more than once. Return true if a duplicate exists anywhere in the array, or false if every element is unique.

Input: nums = [1, 2, 3, 1]
Output: true
Explanation: 1 appears at both index 0 and index 3

Counter-example: nums = [1, 2, 3, 4] → false — all four values are distinct.

Intuition

The problem is asking whether the set of unique values is smaller than the full array. Two fundamentally different strategies exist: sort the array so duplicates end up adjacent and detectable in one scan, or use a hash set that answers "have I seen this before?" in constant time per element. The tradeoff is O(n log n) time with O(1) extra space versus O(n) time with O(n) extra space.

Approach 1 — Sort and Scan

Sorting brings equal values next to each other; a single forward pass then only needs to compare each element to its immediate neighbor.

Sort the array in-place.
Iterate from index 0 to n − 2.
If nums[i] == nums[i + 1], a duplicate has been found — return true.
If the loop finishes without a match, return false.

1def containsDuplicate(nums: list[int]) -> bool:
2    nums.sort()
3    for i in range(len(nums) - 1):
4        if nums[i] == nums[i + 1]:   # adjacent match means duplicate exists
5            return True
6    return False

Time: O(n log n) — dominated by the sort; the scan is O(n).
Space: O(1) extra — sorting is done in-place (Python's Timsort uses O(n) internally, but Java and C++ sort in O(log n) stack space).

Approach 2 — Hash Set

Track every value seen so far in a hash set. When a value is encountered that is already in the set, a duplicate has been found and we can return immediately without scanning the rest of the array.

Initialise an empty hash set called seen.
For each element num in the array, check whether num is already in seen.
If yes, return true.
Otherwise, add num to seen and continue.
If the loop completes, return false.

1def containsDuplicate(nums: list[int]) -> bool:
2    seen = set()
3    for num in nums:
4        if num in seen:     # already encountered this value
5            return True
6        seen.add(num)
7    return False

Time: O(n) — each element is inserted or looked up in the hash set once, each operation is O(1) average.
Space: O(n) — the hash set stores up to n distinct values.

Complexity Summary

Approach	Time	Space	When to use
Sort and Scan	O(n log n)	O(1)	When extra memory is tightly constrained
Hash Set	O(n)	O(n)	Default choice — fastest and returns early on first duplicate

Common Mistakes

Iterating to len(nums) instead of len(nums) - 1 in the sort approach: the comparison nums[i + 1] reads one past the last index when i = n − 1, causing an index-out-of-bounds error.
Checking the set after adding: inserting first and then checking means you'll never detect the second occurrence correctly — the check must happen before the insert.
Relying on len(set(nums)) != len(nums): this is correct but always processes the entire array even if a duplicate is at indices 0 and 1; the explicit loop returns early.
Forgetting that sorting mutates the input array: if the caller owns the array and expects it unchanged, a copy must be made before sorting — the hash set approach avoids this problem entirely.
Using seen.add(num) as a conditional in Python: set.add() always returns None, which is falsy, so if seen.add(num): return True silently does nothing useful.

Contains Duplicate — Solution