Skip to main content
Ace Hired
All coding problems

Contains Duplicate

Easyarrays hashingHash set membershiparraysetduplicate-detection

Maintained by Vikas D, 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.

  1. Loop index i over each position in the array.
  2. For each i, loop index j over every position after i.
  3. If nums[i] equals nums[j], a duplicate exists, so return true.
  4. 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.

  1. Create an empty set called seen.
  2. Iterate over each value n in the array.
  3. If n is already in seen, return true immediately.
  4. Otherwise add n to seen and continue.
  5. 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?

Recommended problems

Build the rest of your prep