What is the brute force approach and complexity for Contains Duplicate?

Check every pair (i, j) for equal values with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Contains Duplicate?

Insert each value into a set; a failed insert means a duplicate with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Contains Duplicate?

Look for key signals in the prompt: "appears at least twice" indicates We only need "have I seen this before?" — a membership question.; "return true / false" indicates No counts or positions needed → a set is enough, not a map.; "any two positions (no distance limit)" indicates Remember **every** earlier value, not just a window of recent ones..

Contains Duplicate

Easy·LeetCode #217Basic Anchor

LeetCode

Jump:

30-Second Mental ModelHash Set membership (seen-before check)

Complexity:O(N²)→O(N)

Key Insight

Walk the array once and keep every value you have passed in an unordered_set. Before adding x, the set already tells you in O(1) whether x was seen. If it was, you found a duplicate.

Core Validity Invariant

nums[i] is a duplicate exactly when it is already in seen — that means it appeared at some earlier index.

Problem

You are given an integer array nums.

Return true if some value appears at least twice in the array. Return false if every value is different.

Input

An integer array nums.

Output

true if any value repeats, otherwise false.

Example 1

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

Output: true

The value 1 appears at index 0 and again at index 3.

Example 2

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

Output: false

All four values are different.

Example 3

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

Output: true

Several values repeat. Finding one repeat is enough.

Constraints

• 1 ≤ nums.length ≤ 10^5
• −10^9 ≤ nums[i] ≤ 10^9

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Do I need to know which value repeats, or how many times, or only whether one repeats?
2.
Does it matter how far apart the two equal values are?
3.
If I walk left to right, what do I need to remember about the values I have already passed?
4.
If the array were sorted, where would two equal values be?
5.
Am I allowed to change the array? Do I care about extra memory?

Brute force approach

Idea

A duplicate is a pair of positions i < j with nums[i] == nums[j]. Try every pair and stop as soon as one matches.

Thinking process

1
The question is about two positions holding the same value.
2
So try every pair: fix i, then compare it with every j after it.
3
If any pair matches, answer true. If no pair matches, answer false.

Code & Implementation

brute.cpp

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();

        // Compare every pair (i, j) with i < j.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
};

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int n = nums.length;

        // Compare every pair (i, j) with i < j.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        n = len(nums)

        # Compare every pair (i, j) with i < j.
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return True

        return False

export function containsDuplicate(nums: number[]): boolean {
    const n = nums.length;

    // Compare every pair (i, j) with i < j.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] === nums[j]) return true;
        }
    }
    return false;
}

Complexity

Time O(N²)Space O(1)

About n²/2 comparisons. With n = 10^5 that is 5·10^9 — too slow when there is no duplicate and we must check every pair.

Better approach

Why brute force is slow

Each element is compared with every element after it, even ones that cannot possibly be equal.

What repeated work are we doing?

We keep asking "is this value equal to that one?" for all n²/2 pairs, with no order to rule pairs out.

What information can we reuse?

Sorting puts equal values together. After that, only the n − 1 neighbour pairs need checking.

New approach

Idea

Sort the array. Equal values now sit next to each other, so a duplicate exists exactly when some nums[i] == nums[i − 1].

Thinking process

1
In the brute force, most comparisons are between values that are obviously far apart.
2
If the array were sorted, a value could only be equal to its neighbour — anything further away is bigger or smaller.
3
So sort once, then one pass over neighbours is enough.

Visual

Only neighbouring pairs in the sorted array are compared.

Sort and compare neighboursnums = [3, 1, 4, 5, 9, 2, 6, 4]step 1/5

before

sorted

State

i: —
answer: —

Sort: equal values become neighbours

After sorting, two equal values cannot have a different value between them, so they must be side by side.

Code & Implementation

better.cpp

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // After sorting, equal values sit next to each other.
        sort(nums.begin(), nums.end());

        // So a duplicate, if any, must be a pair of neighbours.
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] == nums[i - 1]) return true;
        }
        return false;
    }
};

import java.util.Arrays;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        // After sorting, equal values sit next to each other.
        Arrays.sort(nums);

        // So a duplicate, if any, must be a pair of neighbours.
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) return true;
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # After sorting, equal values sit next to each other.
        nums_sorted = sorted(nums)

        # So a duplicate, if any, must be a pair of neighbours.
        for i in range(1, len(nums_sorted)):
            if nums_sorted[i] == nums_sorted[i - 1]:
                return True

        return False

export function containsDuplicate(nums: number[]): boolean {
    // After sorting, equal values sit next to each other.
    const sorted = [...nums].sort((a, b) => a - b);

    // So a duplicate, if any, must be a pair of neighbours.
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i] === sorted[i - 1]) return true;
    }
    return false;
}

Complexity

Time O(N log N)Space O(1)

The sort dominates. std::sort works in place (it uses only O(log N) stack). This changes the input array, which is usually allowed. When memory is tight, this is a perfectly good answer.

Optimized approach

Idea

Walk the array once and keep every value you have passed in an unordered_set. Before adding x, the set already tells you in O(1) whether x was seen. If it was, you found a duplicate.

Start from brute force

The brute force fixes j and scans every earlier i to ask "is nums[j] somewhere before me?"

Find the repeated work

Every new element re-scans all the elements before it. The same earlier values are looked at again and again. If we remember the earlier values in a set, the scan becomes one lookup.

Define the state — what variables do I need?

seen: Set of all values at indices before i.
i: The index we are checking now.

Define validity

nums[i] is a duplicate exactly when it is already in seen — that means it appeared at some earlier index.

Define the transitions — when does each pointer move, and why is it safe?

nums[i] is already in seen

return true

Some earlier index holds the same value. One repeat is all the question asks for.

nums[i] is not in seen

seen.insert(nums[i]) and move on

This value is new so far. Store it so later elements can find it.

The loop ends

return false

Every insert succeeded, so every value was different from all values before it.

What does the current window add to the answer?

Each index either finds its value in the set (answer found) or adds one new value. Every pair i < j with equal values is caught at index j at the latest.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;   // values met so far

        for (int x : nums) {
            // insert(x).second is false when x was already in the set.
            if (!seen.insert(x).second) return true;
        }
        return false;
    }
};

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

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>(); // values met so far

        for (int x : nums) {
            // add(x) returns false when x was already present in the set.
            if (!seen.add(x)) return true;
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()  # values met so far

        for x in nums:
            if x in seen:
                return True
            seen.add(x)

        return False

export function containsDuplicate(nums: number[]): boolean {
    const seen = new Set<number>(); // values met so far

    for (const x of nums) {
        if (seen.has(x)) return true;
        seen.add(x);
    }
    return false;
}

Complexity

Time O(N)Space O(N)

Average O(1) per insert, so O(N) overall. The trade-off: the set can hold up to n values. Sorting uses almost no extra memory but costs O(N log N). Pick based on what matters more — both are accepted.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Check every pair (i, j) for equal values	O(N²)	O(1)
Better	Sort; equal values become neighbours	O(N log N)	O(1)
Optimal	Insert each value into a set; a failed insert means a duplicate	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“appears at least twice”We only need "have I seen this before?" — a membership question.
“return true / false”No counts or positions needed → a set is enough, not a map.
“any two positions (no distance limit)”Remember **every** earlier value, not just a window of recent ones.

Have I seen this value before?+yes / no answer+any distance→Hash Set membership (seen-before check)

This is the anchor of the set-membership sub-pattern: put values in a set, and each "is x present?" question costs O(1). Longest Consecutive Sequence asks the same question about x − 1 and x + 1 instead of x itself, and First Missing Positive asks it about 1, 2, 3, …. Contains Duplicate II adds a distance limit k, which turns the set into a sliding window of the last k values — this problem has no such limit.

Don't make this mistake

Solving Contains Duplicate II instead

✗ seen.insert(nums[i]); if (i >= k) seen.erase(nums[i - k]);

✓ // keep every value; never erase if (!seen.insert(nums[i]).second) return true;

This is a pattern-confusion trap. Contains Duplicate II only counts duplicates at most k apart, so it keeps a window of the last k values. Here there is no distance limit: two equal values at index 0 and index 99999 still count. Erasing old values makes you miss them.

Using a map of counts when a set is enough

✗ unordered_map<int, int> cnt; for (int x : nums) cnt[x]++; for (auto& [v, c] : cnt) if (c > 1) return true;

✓ unordered_set<int> seen; for (int x : nums) if (!seen.insert(x).second) return true;

Counts are not needed — only "seen or not". The map version also always reads the whole array and then loops again, instead of stopping at the first repeat. Pick the smallest structure that answers the question.

Comparing non-neighbours after sorting, or forgetting to sort

✗ for (int i = 1; i < n; i++) if (nums[i] == nums[i - 1]) return true; // unsorted

✓ sort(nums.begin(), nums.end()); for (int i = 1; i < n; i++) if (nums[i] == nums[i - 1]) return true;

The neighbour check is only correct because sorting puts equal values together. On the unsorted [1, 2, 3, 1] no two neighbours are equal, so it wrongly returns false.

Starting the brute-force inner loop at j = 0

✗ for (int j = 0; j < n; j++) if (nums[i] == nums[j]) return true;

✓ for (int j = i + 1; j < n; j++) if (nums[i] == nums[j]) return true;

With j = 0, the pair i == j compares an element with itself, so every array looks like it has a duplicate.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track

C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track

Longest Consecutive Sequence