217. Easy

Contains Duplicate🔗

EasyArrayHash Table·AmazonAppleMicrosoft

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 1:

Input:nums = [1,2,3,1]

Output:true

The element 1 appears both at index 0 and 3.

Example 2:

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

Output:false

Example 3:

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

Output:true

Constraints:

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Hints

Hint 1Can you sort the array to group duplicates together?▼

If you sort the array, any duplicate elements will be adjacent to each other. You can then iterate through the array and check if nums[i] == nums[i+1]. This takes O(N log N) time and O(1) space.

Hint 2Use a HashSet to trade space for time complexity.▼

Instead of sorting, you can utilize a HashSet data structure. As you iterate linearly, insert each element into the Hash Set. If the element already exists in the Hash Set, you have found a duplicate and can return early in O(N) time and O(N) space.

🌐 Real-World Analogy

Event Ticket Scanning

Imagine you are a security guard standing at the entrance to an event. People walk up with their ticket IDs. You want to make sure no line scans the exact same ticket ID twice. To do this efficiently, you keep a list of scanned ticket IDs in your HashTable (or HashSet) scanner. When a new person approaches, you quickly scan their ID. If your device rings because the ID is already in its memory, then you found a duplicate! Otherwise, you save it into memory and let them in. This O(1) checking prevents bottlenecks at the entrance.

Optimal Approach — Hash Set

O(n) Time

🗺️

Single Pass with Hash Set

Time O(n)Space O(n)

We linearly scan the array and add elements to a HashSet, checking if we've already encountered the element.

1Initialize an empty hash set: seen = set().
2For each element nums[i], check if it is in seen.
3If seen has nums[i] → return true immediately.
4If not, add nums[i] to seen.
5If the loop finishes, return false.

Hash Sets provide us with exactly O(1) average lookup and insertion time, minimizing overall execution to O(n).

Array

HashSet { value }

READYPress ▶ or step forward to begin.

✓

—

Array

Executing Code

def containsDuplicate(nums):

    seen = set()

    for i, num in enumerate(nums):

        if num in seen:

            return True

        seen.add(num)

    return False

Discussion

…

Loading comments…

LeetMotion