Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Easy

Contains Duplicate

Contains Duplicate explained: use a hash set to spot a repeated value in one O(n) pass, plus the sorting alternative, tested Python and a live visual.

Also searched as: check if array has duplicates · find duplicate elements in array python

#️⃣

Try it live Free

Hash Tables

Insert keys into the hash table and watch where each lands. When a key you insert is already sitting in its bucket, that is the duplicate this problem is looking for.

Open the playground →

The problem

Given a list of integers nums, return True if any value appears at least twice, and False if every value is distinct.

Inputnums = [1, 2, 3, 1]
OutputTrue

1 appears twice.

Inputnums = [1, 2, 3, 4]
OutputFalse

The key insight

A duplicate means "I have seen this value before". A hash set remembers everything seen so far and answers membership in O(1), so the first time a value is already in the set you can stop.

Brute force first: Comparing every pair is O(n²); sorting first and comparing neighbours is O(n log n).

Step-by-step approach

  1. Create an empty set seen.
  2. For each value x: if x is in seen, return True immediately.
  3. Otherwise add x to seen.
  4. If the loop finishes, every value was new, so return False.

Python solution

PYTHON 3tested
def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Complexity

TimeO(n)
SpaceO(n)

One pass with average O(1) set lookups. The set can grow to hold every element when there is no duplicate.

Common mistakes

Frequently asked questions

What is the time and space complexity of Contains Duplicate?

The hash set solution runs in O(n) time with O(n) extra space. Sorting and checking neighbours is O(n log n) time with O(1) extra space if you may modify the input.

Is len(set(nums)) != len(nums) acceptable?

Yes, it is a correct one-liner with the same O(n) complexity. It cannot stop early, so the explicit loop is slightly faster when a duplicate appears near the start.

What if duplicates only count within distance k?

That variant keeps a sliding window of the last k values in a set, adding the new value and removing the one that falls out of the window.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.