EasyArrayHash TableSortingUpdated Sep 2026

217. Contains Duplicate

Asked at Google, Netflix

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

Array

Companies

2

Problem

You are given an array of integers called nums. Your job is to decide whether any value appears at least twice in the array.

Return true if at least one value shows up two or more times. Return false if every element in the array is different from all the others. The positions do not matter — only the values do.

For example, in [1,2,3,1] the value 1 sits at index 0 and index 3, so the answer is true. In [1,2,3,4] no value repeats, so the answer is false.

Does any value repeat?

12310123The value 1 appears at index 0 and index 3 — aduplicate.
Scan the array and ask: has this value been seen before?

Constraints

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

Examples

Example 1
Inputnums = [1,2,3,1]
Outputtrue
WhyThe value 1 appears at index 0 and again at index 3, so a duplicate exists.
Example 2
Inputnums = [1,2,3,4]
Outputfalse
WhyEach of the four values is different, so nothing repeats.
Example 3
Inputnums = [1,1,1,3,3,4,3,2,4,2]
Outputtrue
WhyMany values repeat here — for instance 1 appears three times — so the answer is true.

Asked At

2 companies
CompanyDifficulty
GoogleEasyView all Google questions →
NetflixEasyView all Netflix questions →

How to Think About It

1

Brute force: compare every pair of elements. Two nested loops, O(n^2) time. Works but way too slow.

2

Better: sort the array first, then scan for adjacent duplicates. O(n log n) time, O(1) space (if sorting in-place). The O(n log n) sort dominates.

3

Optimal: use a hash set. For each element, check if it's already in the set. If yes, return true. If no, add it. O(n) time, O(n) space. The set guarantees uniqueness.

4

Why hash set over hash map: you only need to know IF an element exists, not WHERE it is. A set is simpler and uses less memory per element.

5

Edge cases: empty array (return false), single element (return false), all same (return true).

Optimal Approach

Use a hash set. For each element:

  1. If element is in set, return true (duplicate found).
  2. Add element to set.
  3. After the loop, return false (no duplicates).

Time: O(n) -- one pass. Space: O(n) for the hash set.

Hash set one-pass check

12310123iStep 1 — read 1, it is not in the set, so add itseen123frontbackStep 2 — 2 and 3 are also new, so the set grows to {1,2, 3}12310123iStep 3 — read 1 again, it is already in the set, soreturn trueif x in seen: return trueseen.add(x)
Keep a set of values seen so far. Stop the moment a value is already inside.
ComplexityTime O(n)Space O(n)One pass over the array, and the hash set may hold up to n distinct values.

What Trips People Up in Real Interviews

1

Sorting first and comparing adjacent elements. That's O(n log n). The hash set approach is O(n). The interviewer may ask you to solve it without extra space -- then sorting is the answer.

2

Confusing "at least twice" with "exactly twice." The problem asks if ANY value appears at least twice. One duplicate is enough to return true.

3

Not handling edge cases: empty array (return false), single element (return false). These seem trivial but are easy to forget under pressure.

4

Using a hash map instead of a hash set. A map stores key-value pairs, wasting memory. A set stores just the keys.

5

Trying to solve it without any data structure. Without a set or sorting, you need O(n^2) brute force. There's no O(n) time, O(1) space solution for this problem.

Solution Code

O(n) time
def containsDuplicate(nums):
    return len(nums) != len(set(nums))

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Contains Duplicate problem?

Given an integer array, return true if any value appears at least twice, and false if every element is distinct. This is the simplest version of the duplicate detection pattern and serves as a warm-up for its harder variants.

How do you solve Contains Duplicate?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Contains Duplicate?

Contains Duplicate is asked at Google, Netflix. It is a easy difficulty problem.

What are common mistakes on Contains Duplicate?
  • Sorting first and comparing adjacent elements. That's `O(n log n)`. The `hash set` approach is `O(n)`. The interviewer may ask you to solve it without extra space -- then sorting is the answer.
  • Confusing "at least twice" with "exactly twice." The problem asks if ANY value appears at least twice. One duplicate is enough to return true.
  • Not handling edge cases: empty array (return false), single element (return false). These seem trivial but are easy to forget under pressure.
  • Using a `hash map` instead of a `hash set`. A map stores key-value pairs, wasting memory. A set stores just the keys.
  • Trying to solve it without any data structure. Without a set or sorting, you need `O(n^2)` brute force. There's no `O(n)` time, `O(1)` space solution for this problem.