Contains Duplicate

Easy
10.

Contains Duplicate

EasyArrayHash TableSortingPalantirAirbnb

Contains Duplicate is an easy coding problem on arrays, hash table and sorting, asked in Airbnb and Palantir interviews.

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
Explanation
The value 1 appears at 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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Contains Duplicate — Solution in Python, Java & C++

Contains Duplicate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Contains Duplicate is an easy coding problem on arrays, hash table and sorting, asked in Airbnb and Palantir interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Sorting
  • Asked at: Airbnb, Palantir
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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
Explanation: The value 1 appears at 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

Hints for Contains Duplicate

  1. Hint 1

    Sorting brings duplicates next to each other — that is O(n log n).

  2. Hint 2

    A hash set gives O(n): as you scan, if an element is already in the set you are done.

How to solve Contains Duplicate

Insert each value into a hash set and stop at the first one that is already present.

Approach

  1. Keep an empty set.
  2. For each x: if it is in the set, return true; otherwise add it.
  3. Return false after the loop.

Why it works

A value is in the set exactly when an earlier copy was seen, so the first hit is a duplicate and no hit means all distinct.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Sorting and checking neighbours is O(n log n) with no extra memory — a fair trade when memory is tight.
  • Comparing len(set(nums)) with len(nums) also works but cannot exit early.

Reference solution

Python

def containsDuplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Java

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

C++

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

JavaScript

var containsDuplicate = function(nums) {
    const seen = new Set();
    for (let i = 0; i < nums.length; i++) {
        if (seen.has(nums[i])) return true;
        seen.add(nums[i]);
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets