Contains Duplicate#

Given an array of integers, decide whether any value appears more than once. Return true if at least one number is repeated and false if every element is unique.

Example#

Input: nums = [1, 2, 3, 1] Output: True because the value 1 appears twice.

Input: nums = [1, 2, 3, 4] Output: False because every value is distinct.

Brute force#

Compare every element with every other element using two nested loops. If any pair matches, return true. This wastes time re-scanning the array.

• Time: O(n^2).
• Space: O(1).

Optimal approach#

Track the values you have already seen in a hash set. For each number, check membership first: if it is already in the set, you found a duplicate and can stop. Otherwise add it and continue. Set lookups and inserts are average O(1), so one pass answers the question. A concise alternative is comparing the length of the array to the length of a set built from it.

Python solution#

1def contains_duplicate(nums):
2    seen = set()
3    for num in nums:
4        if num in seen:
5            return True
6        seen.add(num)
7    return False

Complexity#

• Time: O(n), a single pass with constant-time set operations.
• Space: O(n) for the set in the worst case (all unique values).

This problem uses the hashing pattern to trade space for speed. Keep building with the 60-day challenge.