Contains Duplicate easy

Description

Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.

Examples

> Case 1:
    Input:  nums = [1, 2, 3, 1]
    Output: true
 
> Case 2:
    Input:  nums = [1, 2, 3, 4]
    Output: false
 
> Case 3:
    Input:  nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
    Output: true

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

The naïve approaches

• Nested loops — compare every pair. O(n²). Slow.
• Sort first, then walk — O(n log n) time, O(1) extra space if you can mutate the input.
• Hash set — O(n) time, O(n) space.

For interview purposes, the hash-set version is the canonical answer. It’s the simplest and fastest.

Intuition

Walk the array. For each element, ask the set “have I seen you?”. If yes, return true. If no, add it and continue. After the loop, no duplicate exists.

Code

#include <unordered_set>
#include <vector>
using namespace std;
 
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False
 
# Or the one-liner using the size of the set:
# def contains_duplicate(nums):
#     return len(set(nums)) != len(nums)

import java.util.HashSet;
import java.util.Set;
 
public boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (!seen.add(x)) return true;   // add returns false if already present
    }
    return false;
}

A nice trick — the one-liner

Python’s set constructor deduplicates as it builds. So:

def contains_duplicate(nums):
    return len(set(nums)) != len(nums)

If the set has fewer elements than the list, there was a duplicate. It’s a delightful one-liner but uses more memory than needed — it processes the entire array before short-circuiting. In an interview, write the loop version; in a code review, write the one-liner.

Analysis

A textbook “trade space for time” — if you can spend O(n) extra memory, you save O(log n) per element.