Contains Duplicate

Intuition

We need to check whether any number appears more than once.

A brute force nested-loop comparison would be too slow (O(n²)). Instead, we can exploit the fact that sets only store unique elements. If we ever encounter a number we’ve seen before, we found a duplicate.

Approach

1. Initialize an empty set.
2. Traverse the array:

• If the current number is already in the set → return True.
• Otherwise, add it to the set.

1. If traversal finishes with no duplicates → return False.

Proof of Correctness

At each step, the set contains all unique elements seen so far. If a duplicate exists, the second occurrence will be found during traversal because x ∈ set check will succeed. If no duplicate exists, traversal ends with no True. Thus, correctness is guaranteed.

Complexity

• Time: O(n) (average, assuming good hashing).
• Space: O(n) for the set.

Code

export function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();

  for (const num of nums) {
    if (seen.has(num)) {
      return true;
    }
    seen.add(num);
  }

  return false;
}

def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False