Contains Duplicate

Easyarrays hashingHash set membershiparraysetduplicate-detection

Maintained by Vikas Dulgunde, software engineer

You are handed a list of whole numbers. Your job is to report a single yes-or-no answer: does any number appear two or more times anywhere in the list?

Position does not matter. The repeats can sit next to each other or be far apart, and a value can repeat any number of times. The moment a second copy of any value exists, the answer is true.

If you scan the whole list and never find a value you have already seen, every element is distinct and the answer is false. An empty-ish list with one element can never have a duplicate, so it returns false.

Values may be negative or zero, and the list can be long, so the goal is to answer with as little repeated work as possible.

Examples

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

Output: true

The value 1 appears at the start and again at the end, so a duplicate exists.

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

Output: false

Every value is different, so no repeat is found and the answer is false.

Input: nums = [-1, 0, 1, 2, -1]

Output: true

Negatives count too. The value -1 shows up twice, so the result is true.

Constraints

1 <= nums.length <= 100000
-10^9 <= nums[i] <= 10^9
Values may be negative, zero, or positive and need not be sorted

Visible test cases

containsDuplicate([1,2,3,1]) == true
containsDuplicate([1,2,3,4]) == false
containsDuplicate([1,1,1,3,3,4,3,2,4,2]) == true
containsDuplicate([1]) == false
containsDuplicate([-1,0,1,2,-1]) == true

Hints

Hint 1

Ask the simplest question first: for each element, has this exact value already appeared earlier in the list?

Hint 2

Comparing every pair is correct but slow. What data structure answers "have I seen this before?" in constant time?

Hint 3

Walk the array once, keeping a set of values seen so far. Return true the instant the current value is already in the set.

Loading the editor...

Approaches

Brute force pair check

Time O(n^2) · Space O(1)

Compare every element against every later element and return true on the first match.

Loop index i over each position in the array.
For each i, loop index j over every position after i.
If nums[i] equals nums[j], a duplicate exists, so return true.
If the outer loop finishes with no match, return false.

Hash set single pass

Time O(n) · Space O(n)

Track values already seen in a set, which gives constant-time membership checks, so one scan is enough.

Create an empty set called seen.
Iterate over each value n in the array.
If n is already in seen, return true immediately.
Otherwise add n to seen and continue.
If the loop ends without an early return, return false.

Common mistakes

Sorting first and scanning neighbors works but costs O(n log n); the hash set is strictly faster at O(n).
Comparing the length of the array to the size of a set of all values is a clean one-liner, but it builds the whole set even when an early duplicate could let you stop sooner.
Do not assume values are non-negative or small; they range across billions and can be negative, so index-based marking on the input range is not safe.
Returning false too early inside the loop is a common slip; only return false after the entire array has been checked.

Follow-up variations

What changes if you must return the first value that repeats rather than a boolean?
How would you detect a duplicate while using as little extra memory as possible?
If the array is a stream too large to fit in memory, how would your approach adapt?
Contains Duplicate II asks whether a duplicate exists within a fixed index distance k; how would you extend the set idea to a sliding window?

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

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

Output: true

The value 1 appears at the start and again at the end, so a duplicate exists.

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

Output: false

Every value is different, so no repeat is found and the answer is false.

Input: nums = [-1, 0, 1, 2, -1]

Output: true

Negatives count too. The value -1 shows up twice, so the result is true.

Hints

Hint 1

Ask the simplest question first: for each element, has this exact value already appeared earlier in the list?

Hint 2

Comparing every pair is correct but slow. What data structure answers "have I seen this before?" in constant time?

Hint 3

Walk the array once, keeping a set of values seen so far. Return true the instant the current value is already in the set.

Approaches

Brute force pair check

Time O(n^2) · Space O(1)

Compare every element against every later element and return true on the first match.

Loop index i over each position in the array.
For each i, loop index j over every position after i.
If nums[i] equals nums[j], a duplicate exists, so return true.
If the outer loop finishes with no match, return false.

Hash set single pass

Time O(n) · Space O(n)

Track values already seen in a set, which gives constant-time membership checks, so one scan is enough.

Create an empty set called seen.
Iterate over each value n in the array.
If n is already in seen, return true immediately.
Otherwise add n to seen and continue.
If the loop ends without an early return, return false.

Common mistakes

Sorting first and scanning neighbors works but costs O(n log n); the hash set is strictly faster at O(n).

Comparing the length of the array to the size of a set of all values is a clean one-liner, but it builds the whole set even when an early duplicate could let you stop sooner.

Do not assume values are non-negative or small; they range across billions and can be negative, so index-based marking on the input range is not safe.

Returning false too early inside the loop is a common slip; only return false after the entire array has been checked.

Follow-up variations

What changes if you must return the first value that repeats rather than a boolean?

How would you detect a duplicate while using as little extra memory as possible?

If the array is a stream too large to fit in memory, how would your approach adapt?

Contains Duplicate II asks whether a duplicate exists within a fixed index distance k; how would you extend the set idea to a sliding window?

Contains Duplicate

Examples

Constraints

Hints

Approaches

Brute force pair check

Hash set single pass

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Contains Duplicate

Examples

Constraints

Hints

Approaches

Brute force pair check

Hash set single pass

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep