Skip to content
16-Week DSA Roadmap
LeetCode #217EasyProblem 1 of 8

Contains Duplicate

Say whether any number appears more than once in an array.

  • Hash set membership

Before this, know: Arrays and indexes, Hash sets (Set in JavaScript, set in Python)

The problem in plain English

You get a list of numbers called nums. Answer one yes/no question: does any number appear more than once? Return true if some value shows up at least twice, and false if every value is different.

A list is stored as an array: a row of boxes, each with a position number called its index. Indexes start at 0, so the first box is index 0.

Here is a small example, nums = [1, 2, 3, 1]:

nums
  1. 10
  2. 21
  3. 32
  4. 13
The value 1 sits at index 0 and again at index 3, so the answer is true.

And nums = [1, 2, 3, 4] has no repeats, so the answer is false.

The rules that matter:

  • We compare values, not positions. Two different boxes holding the same number count as a duplicate.
  • One repeat is enough. We don’t need to count how many, or say which.
  • On LeetCode the array has at least 1 number and up to 100,000 of them, and the numbers can be negative.

Before you code: think it through

The notebook in that story is a hash set: a collection that remembers values and can answer “is this value in here?” in about one step, no matter how many values it holds. In JavaScript it’s a Set; in Python it’s a set.

seen3 items

look up 1: found

  • 1
  • 2
  • 3
A hash set holding 1, 2 and 3. Asking 'is 1 in here?' gets an instant yes.

Pause and think

nums = [4, 9, 4]. Walk through it with the notebook. At which index do you notice the duplicate, and what is in the notebook at that moment?

Approach 1: Brute force

Brute force means trying every possibility. Here that means comparing every number with every number that comes after it. We use two pointers (variables that remember a position): i for the first number and j for the second.

Brute force: compare every pair

nums = [1, 2, 3, 1]

nums
  1. 10
  2. 21
  3. 32
  4. 13
variables
comparisons so far
0
answer
—
  • First number (i)
  • Second number (j)
  • Equal pair

Pick nums[0] = 1. Compare it with every number after it.

Step 1 / 5

Which line is running?

function containsDuplicate(nums) {Running now:   for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] === nums[j]) {        return true;      }    }  }  return false;}

Brute force

function containsDuplicate(nums) {  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] === nums[j]) {        return true;      }    }  }  return false;}
def contains_duplicate(nums):    for i in range(len(nums)):        for j in range(i + 1, len(nums)):            if nums[i] == nums[j]:                return True    return False

j starts at i + 1, so we never compare a number with itself and never compare the same pair twice.

Why is it slow?

Count the comparisons when there are no duplicates (the worst case, because we can’t stop early). With 4 numbers: 3 + 2 + 1 = 6 comparisons.

With 100,000 numbers (LeetCode’s limit): 99,999 + 99,998 + … + 1, which is about 100,000 × 100,000 ÷ 2 = 5,000,000,000 comparisons. Five billion! That takes far too long.

We describe this kind of growth with Big-O notation, a short way of saying how the work grows as the input grows. Work that grows like n × n is O(n²): double the input and the work goes up four times.

A middle ground: sort first

If we sort the numbers, equal numbers end up side by side. Then one walk that compares each number with its left neighbour finds any duplicate.

Sort, then compare neighbours

function containsDuplicate(nums) {  const sorted = [...nums].sort((a, b) => a - b);  for (let i = 1; i < sorted.length; i++) {    if (sorted[i] === sorted[i - 1]) {      return true; // equal numbers end up side by side    }  }  return false;}
def contains_duplicate(nums):    s = sorted(nums)    for i in range(1, len(s)):        if s[i] == s[i - 1]:            return True  # equal numbers end up side by side    return False

Sorting costs about n × log n steps, written O(n log n). That’s much better than O(n²): for 100,000 numbers it’s roughly 1.7 million steps instead of 5 billion. (Log n is “how many times you can halve n before reaching 1”; for 100,000 that’s about 17.) But we can do better still, with no sorting at all.

The pattern: hash set membership

The brute force spends all its time searching: for each number, “is there another copy anywhere?”. A hash set turns that search into a single question with an instant answer.

Pattern

Hash set: have I seen this?

Template

Use it when: you need to know whether a value has appeared before: duplicates, repeats, 'already visited'.

Signal words

  • “contains duplicate”
  • “appears twice”
  • “any repeated”
  • “all unique”
  • “first repeated”

Approach 2: One pass with a hash set

  1. Create an empty hash set called seen.
  2. Walk through nums one number at a time. Call the current number num.
  3. Ask: is num already in seen? If yes, return true immediately.
  4. If not, add num to seen and move on.
  5. If the loop ends, nothing repeated. Return false.

Press Play, or click the player and use the arrow keys. Watch the set grow underneath the array, and watch the code panel: the highlighted line is the one running at that moment. Try the edge cases too: a single number, and negatives.

One pass with a hash set

nums = [1, 2, 3, 1]

nums
  1. 10
  2. 21
  3. 32
  4. 13
seen0 items
    empty
variables
num
—
answer
—
  • Looking at now
  • Already in the set
  • Seen before (duplicate)
  • Not seen yet
  • Just added to the set

Start with an empty hash set called "seen". It will remember every number we walk past, and it can answer "have I seen this?" in about one step.

Step 1 / 13

Which line is running?

function containsDuplicate(nums) {Running now:   const seen = new Set(); // every number we have passed so far  for (const num of nums) {    if (seen.has(num)) {      return true;    }    seen.add(num);  }  return false;}

Notice that in “Example 1” we stop at index 3 and never need to finish the loop. In “No duplicates” we have to look at every number before we can be sure the answer is false.

The code, line by line

One pass with a hash set

function containsDuplicate(nums) {  const seen = new Set(); // every number we have passed so far  for (const num of nums) {    if (seen.has(num)) {      return true;    }    seen.add(num);  }  return false;}
def contains_duplicate(nums):    seen = set()  # every number we have passed so far    for num in nums:        if num in seen:            return True        seen.add(num)    return False

The two versions line up until line 5; JavaScript then has a closing brace } on line 6, so its later line numbers run one ahead of Python’s.

  • Line 1: define the function. (On LeetCode, JavaScript uses var containsDuplicate = function(nums) and Python wraps it in class Solution as def containsDuplicate(self, nums). The body is the same.)
  • Line 2: create an empty set. new Set() in JavaScript, set() in Python. Careful: in Python {} makes an empty dict, not an empty set.
  • Line 3: loop over the values directly. for (const num of nums) / for num in nums hands us each number in turn; we don’t need the index here.
  • Line 4: the key question. seen.has(num) / num in seen takes about one step, however big the set is. This is the line that makes the solution fast.
  • Line 5: if we’ve seen it, we’ve found a duplicate. Return true straight away.
  • Line 7 (JS) / line 6 (Python): otherwise remember the number. Adding to a set also takes about one step. Adding a value that’s already there would do nothing, but we never get that far, because line 4 catches it first.
  • Line 9 (JS) / line 7 (Python): the loop finished without a repeat, so every number is different. Return false.

Dry run

Let’s trace nums = [1, 2, 3, 1] by hand. Each row is one trip around the loop.

indexnumnum in seen?what happensseen afterwards
01no (empty)add 1{1}
12noadd 2{1, 2}
23noadd 3{1, 2, 3}
31yesreturn true(we stop here)
nums = [1, 2, 3, 1]

The index 3 row is the moment the notebook pays off: one lookup tells us that 1 has been seen before, without comparing it against 2 and 3 at all.

Complexity

Brute force

Time

O(n²)

Every number is compared with every number after it: about n × n ÷ 2 comparisons.

Space

O(1)

Only the two pointers i and j. O(1) means 'a fixed amount, however long the input'.

Sort first

Time

O(n log n)

Sorting dominates. The neighbour walk afterwards is just n steps.

Space

O(n)

We sort a copy so we don't change the caller's array. (Sorting in place can bring this down, but it changes the input.)

One pass with a hash set

Time

O(n)

We look at each number once, and each set lookup or insert takes about one step. 100,000 numbers ≈ 100,000 steps.

Space

O(n)

With no duplicates, the set ends up holding every number.

As in Two Sum, we trade memory for time: the set costs extra space, and in return the work grows in a straight line with the input instead of as a square.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Restate: “Return true if any value appears at least twice.”
  2. Brute force: “Compare every pair: O(n²) time, O(1) space.”
  3. Better: “Sort, then compare neighbours: O(n log n).”
  4. Best: “A hash set gives O(1) lookups, so one pass is O(n) time, O(n) space.”
  5. Trace a short example, like the dry run above.

Likely follow-up questions:

  • “What if you can’t use extra memory?” Sort in place and compare neighbours: O(n log n) time, O(1) extra space.
  • “What if duplicates only count within distance k?” That’s Contains Duplicate II: keep a set of only the last k numbers (a sliding window, week 2).
  • “Return the duplicate value?” Return num instead of true.

Related problems:

  • Valid Anagram (this week): the next step up, counting how many times each value appears instead of just “seen or not”.
  • Two Sum (this week): a hash map that remembers what we’ve seen and where.
  • Longest Consecutive Sequence (this week): uses a hash set for instant “is x here?” questions.