Contains Duplicate

You are given an array of integers nums. Return true if some value occurs at least twice, and false if every value is distinct.

Examples

Input:  nums = [1, 2, 3, 1]
Output: true          (1 appears twice)

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

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

Constraints

• 1 ≤ nums.length ≤ 10⁵
• −10⁹ ≤ nums[i] ≤ 10⁹

Explanation

Intuition

A duplicate means “I have seen this value before”. If we can remember every value seen so far and check membership instantly, one pass is enough.

Brute force — O(n²)

Compare every pair (i, j) with i < j. Correct, but 10⁵ elements means ~5 × 10⁹ comparisons: far too slow.

Better — sort, O(n log n)

After sorting, equal values sit next to each other, so check neighbours. Uses O(1) extra space (if sorting in place), but changes the input and costs n log n.

Optimal — hash set, O(n)

Walk the array; for each value, if it is already in the set, return true; otherwise add it. If the loop ends, there were no duplicates.

Complexity

• Time: O(n) on average (hash set operations are O(1) expected).
• Space: O(n) for the set.