Coding problem · Easy · Arrays & Hashing

Contains Duplicate

Easy Algorithms & data structures Seen at Amazon, Apple, Adobe

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

Example 1

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

Example 2

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

Constraints

1 <= nums.length <= 10^5

Hints

Hint 1

A set remembers what you've seen in O(1) per lookup.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Add each value to a set; if it's already there, you found a duplicate. Alternatively compare set(nums).size with nums.length.

Reference solution

function containsDuplicate(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

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

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

<?php

function containsDuplicate(array $nums): bool
{
    return count(array_unique($nums)) !== count($nums);
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) if (!seen.add(x)) return true;
        return false;
    }
}

Follow-up questions

Contains Duplicate II: duplicates within distance k (sliding window of a set).