EasyBlind75ArrayHash Table

Contains Duplicate

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.

Examples

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

Element 1 appears twice.

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

All elements are distinct.

Constraints

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

Approaches

Compare every pair of elements using nested loops.

CodeT: O(n^2) | S: O(1)
def contains_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Sort the array and check adjacent elements for duplicates.

CodeT: O(n log n) | S: O(1)
def contains_duplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Use a hash set to track seen elements. If an element is already in the set, return true.

Diagram

nums = [1,2,3,1] i=0: seen={1} i=1: seen={1,2} i=2: seen={1,2,3} i=3: 1 in seen -> return True
CodeT: O(n) | S: O(n)
def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Complexity Comparison

Brute Force
T: O(n^2)S: O(1)

Compare every pair of elements using nested loops.

Sorting
T: O(n log n)S: O(1)

Sort the array and check adjacent elements for duplicates.

Hash Set
T: O(n)S: O(n)

Use a hash set to track seen elements. If an element is already in the set, return true.

Common Mistakes

Using len(set(nums)) == len(nums) which creates unnecessary extra space

Off-by-one errors when comparing adjacent elements after sorting

Forgetting to handle empty arrays or single-element arrays

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems