Contains Duplicate (opens in a new tab) 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

Example 1:

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

Output: true

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

Summary

The basic idea of the solution is to create a Set object set from the input array nums, which removes all duplicates and only keeps distinct elements. If the size of set is not equal to the length of nums, then there must be at least one element that appears more than once, so we return true. Otherwise, every element is distinct, so we return false.

Solution

In TypeScript

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

In Python

def containsDuplicate(nums: List[int]) -> bool:
    return len(set(nums)) != len(nums)

Step-by-step explanation

1. Create a new Set object set from the input array nums using the Set constructor. The number in the Set constructor is optional, and it specifies the type of the elements stored in the Set. In this case, we are specifying that the elements are numbers.

2. Check if the size of set is not equal to the length of nums using the size property of set and the length property of nums.

3. If the size of set is not equal to the length of nums, return true, otherwise return false.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array nums. This is because creating a Set object from an array has a time complexity of O(n), and the size and length property lookups are O(1).

Space Complexity

The space complexity of this solution is also O(n), because in the worst case scenario where there are no duplicates in the input array, the Set object set will have the same length as nums.

Variations

There are actually several different algorithms that can be used to solve this problem, each with its own time and space complexity. Here are a few variations:

Brute force

We can use a nested loop to compare every pair of elements in the input array nums and check if any pair are equal. This approach has a time complexity of O(n^2) and a space complexity of O(1).

In TypeScript

function containsDuplicate(nums: number[]): boolean {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                return true;
            }
        }
    }
    return false;
}

In Python

def containsDuplicate(nums: List[int]) -> bool:
		for i in range(len(nums) - 1):
				for j in range(i + 1, len(nums)):
						if nums[i] == nums[j]:
								return True
		return False

Sorting

We can sort the input array nums in ascending order and then check if any adjacent elements are equal. If so, return true, otherwise return false. This approach has a time complexity of O(n log n) due to the sorting step.

In TypeScript

function containsDuplicate(nums: number[]): boolean {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            return true;
        }
    }
    return false;
}

In Python

def containsDuplicate(nums: List[int]) -> bool:
		nums.sort()
		for i in range(1, len(nums)):
				if nums[i] == nums[i - 1]:
						return True
		return False

Hash table

We can use a hash table to store the frequency of each element in the input array nums, and then check if any element has a frequency greater than 1. This approach has a time complexity of O(n) and a space complexity of O(n).

In TypeScript

function containsDuplicate(nums: number[]): boolean {
    const freq = new Map<number, number>();
    for (const num of nums) {
        freq.set(num, (freq.get(num) ?? 0) + 1);
        if (freq.get(num) > 1) {
            return true;
        }
    }
    return false;
}

In Python

def containsDuplicate(nums: List[int]) -> bool:
		freq = {}
		for num in nums:
				freq[num] = freq.get(num, 0) + 1
				if freq[num] > 1:
						return True
		return False