Contains Duplicate

Difficulty: Easy

Problem

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

Example

Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The number 1 appears at index 0 and index 3.

Brute-force approach

Compare every element with every other element to find duplicates.

Steps

1. Pick each element
2. Compare with all remaining elements
3. If match found, return true
4. If no matches, return false

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

• Checking every pair is slow
• Redundant comparisons
• Gets very slow with large arrays

Optimal approach

Key insight: A Set only stores unique values. If an element is already in the Set, it's a duplicate!

Use a Set to track seen elements - if we try to add a duplicate, we found one!

Steps

1. Create an empty Set
2. For each number, check if it's in the Set
3. If yes, return true (duplicate found)
4. If no, add it to the Set

Time complexity: O(n) · Space complexity: O(n)