Contains Duplicate

217. Contains Duplicate

Easy

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

ArrayHash TableSorting

View Problem

Problem Statement

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
Explanation: The element 1 occurs at the indices 0 and 3.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.

Example 3:

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Try It Yourself

TypeScript

function containsDuplicate(nums: number[]): boolean {
    // Your solution here
}

Go

func containsDuplicate(nums []int) bool {
    // Your solution here
}

Solution

Click to reveal solution

Use a Set to track unique elements and compare the length with the original array.

TypeScript Solution

function containsDuplicate(nums: number[]): boolean {
  return nums.length !== Array.from(new Set(nums)).length;
}

Time:O(n)

Space:O(n)

Go Solution

func containsDuplicate(nums []int) bool {
  set := map[int]bool{}

  for _, num := range nums {
      set[num] = true
  }

  return len(nums) != len(set)
}

Time:O(n)

Space:O(n)

Algorithm:

1. Create a set/map to store unique elements
2. Iterate through the array and add each element to the set
3. Compare the length of the original array with the set size
4. If they differ, duplicates exist; return true
5. If they're equal, all elements are distinct; return false

Alternative Approach (Early Exit): For better performance in worst-case scenarios, you could also iterate once and check for duplicates immediately:

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;
}