Contains Duplicate

Contains Duplicate looks easy. And it is. But that is exactly why interviewers like it. They want to see if you reach for the slow answer or the fast one. The same question can be solved in three very different ways. Picking the fast one shows you think about speed.

🎯 The Problem

You get an array of numbers. Say if any number shows up more than once.

• Return true if even one number repeats.
• Return false if every number is different.
• A duplicate is a value that appears again later in the same array.

Let us say the array is [1, 2, 3, 1]. The number 1 appears at the start and again at the end. So a number repeats. That means the answer is true.

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

Explanation: the number 1 appears at index 0 and again at index 3

If the array were [1, 2, 3, 4], every number is different. So the answer would be false.

Here is a picture of what we are scanning for. We walk across the array and look for any value we have met before.

🐢 Approach 1: Compare Every Pair (Brute Force)

The idea in one line: compare each number with every number after it.

The idea:

• Take each number.
• Compare it with every later number.
• If any two match, you found a duplicate.

How it works:

• One loop picks a number.
• A second loop scans the numbers after it.
• The moment two are equal, return true.

Why it is weak:

• For every number you scan most of the array again.
• Two nested loops over n items means about n times n steps.
• That is O(n²) time. Slow on a big array.

Here is the brute-force code for that idea:

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


print(contains_duplicate([1, 2, 3, 1]))

🪜 Approach 2: Sort Then Scan Neighbors (Better)

The idea in one line: sort first, then equal numbers sit side by side.

The idea:

• Sort the array.
• After sorting, any equal numbers become neighbors.
• So one loop comparing neighbors is enough.

How it works:

• Sort the numbers.
• Walk once and compare each number with the one before it.
• Equal neighbors mean a duplicate, so return true.
• Reach the end with no match, return false.

Why it is mixed:

• Sorting is O(n log n). Faster than brute force, slower than the next idea.
• It changes the order of the array.
• But it adds almost no extra memory, so it helps when memory is tight.

Here is the sorting code for that idea:

def contains_duplicate(nums):
    nums = sorted(nums)

    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True

    return False


print(contains_duplicate([1, 2, 3, 1]))

⚡ Approach 3: One Pass With a Hash Set (Best)

The idea in one line: remember every number you have seen, then check before adding.

The idea:

• Keep a hash set of numbers you have already met.
• A hash set holds unique values and checks membership almost instantly.
• See a number that is already inside, and it is a duplicate.

How it works:

• For each number, ask the set: have I seen this before?
• If yes, return true.
• If no, add the number and move on.

Why it is fast:

• The set lookup is almost instant.
• You walk the array just one time. That is O(n).
• The price is extra memory to hold the seen numbers. That is O(n).

Here is a dry-run of the hash set idea on [1, 2, 3, 1].

Steps to Solve

1. Create an empty hash set to store numbers you have seen.
2. Walk through the array one number at a time.
3. Ask the set if it already holds this number.
4. If it does, return true right away. You found a duplicate.
5. If it does not, add the current number to the set.
6. If the loop finishes with no match, return false.

#include <stdio.h>
#include <string.h>

#define SIZE 1009  // a prime size for the hash table

int keys[SIZE];
int used[SIZE];

// turn a number into a table slot (handles negatives too)
int hashIndex(int key) {
    long h = ((long)key % SIZE + SIZE) % SIZE;
    while (used[h] && keys[h] != key) {
        h = (h + 1) % SIZE;  // linear probing
    }
    return (int)h;
}

int containsDuplicate(int nums[], int n) {
    memset(used, 0, sizeof(used));
    for (int i = 0; i < n; i++) {
        int slot = hashIndex(nums[i]);
        if (used[slot]) {        // this number was seen before
            return 1;            // 1 means true
        }
        keys[slot] = nums[i];    // remember this number
        used[slot] = 1;
    }
    return 0;                    // 0 means false
}

int main(void) {
    int nums[] = {1, 2, 3, 1};
    int n = 4;
    printf("%s\n", containsDuplicate(nums, n) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;  // holds numbers we have met
    for (int num : nums) {
        if (seen.count(num)) {   // already in the set
            return true;
        }
        seen.insert(num);        // remember this number
    }
    return false;
}

int main() {
    vector<int> nums = {1, 2, 3, 1};
    cout << (containsDuplicate(nums) ? "true" : "false") << endl;
    return 0;
}

true

import java.util.HashSet;
import java.util.Set;

public class ContainsDuplicate {
    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();  // holds numbers we have met
        for (int num : nums) {
            if (seen.contains(num)) {   // already in the set
                return true;
            }
            seen.add(num);              // remember this number
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 1 };
        System.out.println(containsDuplicate(nums));
    }
}

true

def contains_duplicate(nums):
    seen = set()              # holds numbers we have met
    for num in nums:
        if num in seen:       # already in the set
            return True
        seen.add(num)         # remember this number
    return False


nums = [1, 2, 3, 1]
print(contains_duplicate(nums))

True

function containsDuplicate(nums) {
  const seen = new Set(); // holds numbers we have met
  for (const num of nums) {
    if (seen.has(num)) {  // already in the set
      return true;
    }
    seen.add(num);        // remember this number
  }
  return false;
}

const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));

true

Let us read the Python version line by line and explain why each line is there.

def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

The line seen = set() creates an empty set. We need a place to remember numbers we have met. A set is perfect because it checks membership almost instantly.

The line for num in nums walks through the array one number at a time. We only need one pass, so one simple loop is enough.

The line if num in seen is the key check. It asks the set if this number is already inside. This lookup is O(1) on average, which is why the whole solution is fast.

The line return True runs the moment we find a repeat. We do not need to keep going. One duplicate is all the question asks for.

The line seen.add(num) runs only when the number is new. We store it so future numbers can be checked against it.

The final return False runs only if the loop finishes without ever finding a repeat. That means every number was unique.

⏱️ Time and Space Complexity

The brute force uses two loops, so it is slow but needs no extra memory. Sorting is faster but still slower than a single pass, and it changes the array order. The hash set uses one loop and almost instant lookups, so it is the fastest. It needs extra memory to hold the seen numbers. So you trade a little memory to reach O(n) time.

🧩 Key Takeaways

• ✅ The trick is to remember numbers you have already seen, so you spot a repeat the moment it comes back.
• ✅ A hash set gives almost instant lookups, so the whole thing runs in O(n) time.
• ✅ Sorting also works and uses no extra memory, but it costs O(n log n) and changes the array order.
• ✅ Brute force is the easy idea but it runs in O(n²), so avoid it for big arrays.
• ✅ Return true the instant you find a repeat. You do not need to scan the rest.

🚀 What’s Next?

• Two Sum
• Product of Array Except Self