173. Contains Duplicate

Track values we have already seen in a hash set. The first time a number is already present, we have found a duplicate.

Walk-through

1. Create an empty hash set seen.
2. Iterate over each number num in nums.
3. If num is already in seen, a duplicate exists — return true.
4. Otherwise add num to seen and continue.
5. If the loop finishes with no repeats, every element was distinct — return false.

Worked example

For nums = [1, 2, 3, 1]:

• 1 → not in set → add 1 → {1}
• 2 → not in set → add 2 → {1, 2}
• 3 → not in set → add 3 → {1, 2, 3}
• 1 → already in set → return true.

Why not sort?

Sorting first (O(n log n)) then scanning adjacent equal pairs also works with O(1) extra space, but the hash-set pass is O(n) time. We trade O(n) space for the faster scan.

Complexity

• Time: O(n) — single pass, each hash operation is O(1) average.
• Space: O(n) — the set stores up to n values.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                return true;
            }
        }
        return false;
    }
}