Contains Duplicate

1. Problem & Core Objective

The problem

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

Input:  nums = [1, 2, 3, 1]        Output: true     (1 appears twice)
Input:  nums = [1, 2, 3, 4]        Output: false    (all distinct)
Input:  nums = [1, 1, 1, 3, 3]     Output: true

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

What the interviewer is actually testing

This question takes about 90 seconds to solve. That is the point — it is a warm-up that filters on communication, not difficulty.

What they are watching for:

1. Do you reach for a hash set immediately? This is the most basic "I have seen this before" question there is.
2. Can you articulate the time/space trade-off? There are three valid solutions with genuinely different profiles. A candidate who gives one and stops looks narrow; one who names all three and picks looks senior.
3. Do you ask about constraints before coding? Memory limits change the right answer here.

The trap is treating it as trivial. Say "hash set, done" and you've skipped the only part being marked.

2. First-Principles Thought Process

Step 1 — Read the constraints, name the budget

n can be 10^5.

• O(n²) → 10^10 operations. Far too slow.
• O(n log n) → about 1.7 × 10^6. Fine.
• O(n) → 10^5. Trivially fine.

So both O(n log n) and O(n) are acceptable, which is the hint that multiple solutions exist and the trade-off is the discussion.

Note also -10^9 <= nums[i] <= 10^9. The value range is huge, so you cannot use a counting array indexed by value — that would need 2 billion slots. This rules out the int[26]-style trick that works in Valid Anagram.

Step 2 — State the brute force and find its waste

The obvious approach compares every pair:

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

Now ask the key question: what is the inner loop actually doing?

It is searching the rest of the array for a specific value. And searching is the thing hash structures make instant.

Step 3 — Reframe the question

Rewrite the problem as a question asked once per element:

"Have I seen this exact value before?"

If yes at any point, there's a duplicate. So walk the array once, and remember everything seen.

"Remember a set of values, ask membership in O(1)" is precisely a HashSet.

Step 4 — Consider the alternative framing

There's a second angle worth knowing, because it produces a genuinely different solution:

"Duplicates are equal values. Equal values, once sorted, are adjacent."

So sorting turns a global search into a local one — just compare neighbours. That costs O(n log n) time but needs no extra memory.

Two valid reframings, two solutions, different trade-offs. That is the whole question.

3. Solution Paths

Approach 1 — Brute force: check every pair

public boolean containsDuplicate(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}

How it works. For each index i, scan everything after it looking for a match. j starts at i + 1 so no pair is checked twice and nothing is compared with itself.

• Time: O(n²) — roughly n²/2 comparisons.
• Space: O(1).

Why it's rejected: at n = 10^5 that's 5 × 10^9 comparisons — around a minute. Name it, give the complexity, move on. Never write it out unless asked.

Counter-questions on this approach

⭐ "That's O(n²). What is the inner loop actually doing?"

It's searching the rest of the array for one specific value. That's the observation that unlocks everything — searching is exactly what a hash structure makes instant. So I can replace the inner loop with a lookup into something I build as I go.

"Would it actually pass at n = 10^5?"

No. That's roughly 5 × 10^9 comparisons — on the order of a minute. It's correct but not submittable.

Approach 2 — Sort, then check neighbours

public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) return true;
    }
    return false;
}

How it works. After sorting, equal values sit next to each other. So a single pass comparing each element with its predecessor finds any duplicate.

Starting at i = 1 and looking back at i - 1 avoids reading past the end.

Trace on [3, 1, 3, 4]:

• Time: O(n log n) — dominated by the sort.
• Space: O(1) extra if you may modify the input, O(log n) for the sort's internal stack.

When this is the right answer: when memory is tight. It's the only approach here that doesn't allocate proportional to n.

The caveat to mention: it mutates the caller's array. Always ask whether that's acceptable. If not, you must copy first — and then you've spent the O(n) memory anyway, making the hash set strictly better.

Counter-questions on this approach

⭐ "You've just mutated the caller's array. Is that allowed?"

I'd need to ask. If it isn't, I have to clone first — and then I've spent O(n) memory anyway, which removes this approach's only advantage over the hash set.

⭐ "Why sort at all, when the question only asks a yes/no?"

Fair challenge. Sorting produces a total ordering of all n elements, which is far more information than "does a duplicate exist". I'm paying a log n factor for something I discard. I'd only choose this when memory is the binding constraint.

"Can this exit early the way a hash set can?"

No, and that's a structural disadvantage. No adjacent comparison is meaningful until the sort is complete, so it always does the full O(n log n) work even when the duplicate is in the first two elements.

Approach 3 — Hash set (optimal)

public boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) {
        if (!seen.add(n)) return true;    // add returned false => already present
    }
    return false;
}

How it works. Walk the array once. For each value, try to add it to the set. HashSet.add returns false when the element was already present — so a failed add is a duplicate detection.

Trace on [1, 2, 3, 1]:

• Time: O(n) — one pass, O(1) per lookup on average.
• Space: O(n) — worst case the set holds every element.

The add return value matters. The longer form does the same work twice:

if (seen.contains(n)) return true;   // lookup 1
seen.add(n);                         // lookup 2  — hashes n all over again

Using add's boolean collapses test-and-insert into one hash computation. It's a small thing, and interviewers notice it.

Early exit is the real-world win. On [1, 1, 2, 3, ..., 100000] this returns after two elements. The sorting approach would sort all 100,000 first.

Counter-questions on this approach

⭐ "Is HashSet.add really O(1)? What's the worst case?"

O(1) average, not worst case. If every key hashed into the same bucket, each operation would degrade into a linear scan of that bucket. Java mitigates this by converting oversized buckets into balanced trees, so the true worst case is O(log n) rather than O(n). With Integer keys — whose hashCode is the identity function — pathological collisions don't arise in practice. The precise claim is "O(n) expected".

⭐ "You've traded O(n) memory for that speed. Is that acceptable here?"

Nothing in the constraints forbids it, and at n = 10^5 the set holds around 400KB of boxed Integers — fine. If memory were constrained I'd switch to the sorting approach and accept O(n log n).

"Why if (!seen.add(n)) rather than contains then add?"

add returns false when the element was already present, so test-and-insert happens in one hash computation instead of two. Same complexity, half the work.

"Your loop boxes every int into an Integer. Does that matter?"

It's a real allocation cost, and it's part of why the theoretically-slower sort can win on small inputs. Eliminating it needs a primitive-specialized set from a library like fastutil — worth knowing, not worth hand-rolling here.

Approach 4 — One-liner (know it, don't lead with it)

public boolean containsDuplicate(int[] nums) {
    return Arrays.stream(nums).distinct().count() < nums.length;
}

If the count of distinct values is less than the total, something repeated.

Do not open with this. It shows API familiarity but hides the algorithm, and it has no early exit — it always processes every element. Offer it as an aside after your real answer.

Counter-questions on this approach

⭐ "If this is one line, why not lead with it?"

Because it hides the algorithm — the interviewer learns nothing about whether I understand the trade-off. It also has no early exit: distinct() processes every element even when the duplicate is at index 1. It's a reasonable aside after the real answer, not the answer itself.

Comparison

4. Why the Optimal Wins

Hash set vs brute force. The brute force re-scans the array for every element. The hash set builds a searchable structure as it goes, so each element is examined once instead of n times. This is the fundamental trade of the whole section: O(n) memory buys the removal of an entire loop.

Hash set vs sorting. Sorting does strictly more work than the problem requires. It produces a total ordering of all n elements — but the question only asks a yes/no about existence. You are computing a full ranking to answer a boolean. The hash set computes exactly what's needed and nothing more.

That's a useful general principle to voice:

Sorting is often the "obvious" O(n log n) fallback, but if the question doesn't need order, hashing usually beats it.

When sorting is genuinely better: memory-constrained environments, or if the array is already sorted (then it's O(n) with no allocation and the hash set is pure overhead). Asking "is the input sorted?" is worth ten seconds.

Why O(n) is the floor. You must look at every element at least once — if you skip one, an adversary puts the duplicate there. So O(n) time is optimal, and this solution achieves it.

5. Java Prerequisites

HashSet.add returns a boolean

Set<Integer> set = new HashSet<>();
set.add(5);        // true  — was not present, inserted
set.add(5);        // false — already present, nothing changed

The idiom:

if (!seen.add(n)) return true;      // "add failed" = "already there" = duplicate

remove mirrors it — true only if something was actually removed.

Autoboxing in the loop

for (int n : nums) {
    seen.add(n);        // int is autoboxed into Integer here
}

nums is int[] (primitives) but Set<Integer> holds objects, so Java boxes each value. That's a real allocation cost — one of the reasons the theoretical O(n) can lose to O(n log n) sorting on small inputs.

To avoid boxing entirely you'd need a primitive-specialized set (Eclipse Collections, fastutil) — worth mentioning, never worth implementing in an interview.

Arrays.sort on primitives

Arrays.sort(nums);       // ascending; dual-pivot quicksort

For int[] there is no comparator overload — primitives can't take one. Arrays.sort(nums, cmp) doesn't compile. See 04 §5.1.

Pre-sizing the set

Set<Integer> seen = new HashSet<>(nums.length * 4 / 3 + 1);

A HashSet resizes and rehashes when it gets about 75% full. Pre-sizing avoids that. A micro-optimization — mention it, don't clutter your solution with it.

6. Interview Communication Guide

Clarifying questions

Ask these before writing anything. Each one changes the right answer:

1. "Can I modify the input array?" — decides whether sorting is on the table.
2. "Is there a memory constraint?" — if yes, sorting wins despite being slower.
3. "Is the array already sorted, or roughly sorted?" — if so, the neighbour scan is O(n) with no allocation.
4. "Can it be empty?" — the constraints say n >= 1, but confirming shows care.

The pitch — before you write code

"The brute force compares every pair, which is O(n²) — too slow for n up to 10⁵.

But notice the inner loop is just searching for a value I've already passed. That's what a hash set makes O(1). So I'll walk the array once, adding each element to a set, and return true the moment an add fails — because a failed add means it was already there. That's O(n) time and O(n) space.

There's also a sorting approach: sort, then check adjacent pairs, since equal values become neighbours. O(n log n) time but O(1) space. I'd pick that if memory were constrained or the input were already sorted.

I'll go with the hash set since it's optimal in time and exits early. Shall I code it?"

That's about 40 seconds and covers brute force, optimal, alternative, trade-off, and a decision.

Edge cases to raise proactively

The value-range point is the one worth volunteering: "Values go up to 10⁹, so a counting array indexed by value isn't viable — that'd be 2 billion slots. Hashing handles the sparse range fine." It shows you read the constraints rather than pattern-matching.

What a strong answer sounds like at the end

"Time O(n) — one pass, and each HashSet.add is O(1) on average because hashing jumps straight to a bucket. Worst case is O(n) per operation if every key collided, but that doesn't happen with Integer's hash.

Space O(n) — worst case is all-distinct input, where the set ends up holding every element."

Claim → mechanism → worst case. That pattern is worth using on every complexity statement you make.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

"What if the array is enormous — won't fit in memory?"

Stream it in chunks, or use a Bloom filter — a probabilistic structure with a small false-positive rate but no false negatives. So "not a duplicate" is certain, and "duplicate" needs confirmation. Constant memory for a tunable error rate.

"What if we need the duplicated value, not just a boolean?"

Return n instead of true in the same loop — no complexity change.

"What if every element appears exactly twice except one?"

XOR everything. Pairs cancel (x ^ x == 0), leaving the unpaired value. O(n) time, O(1) space. That's Single Number (Section 17) — see 22 — Bit Manipulation.

⭐ "Contains Duplicate II — within distance k?"

Slide a window of size k over the array, keeping a HashSet of exactly the last k elements. Remove the element leaving the window as you advance. Still O(n) time, O(k) space. This is the bridge to Sliding Window.

"Contains Duplicate III — values within t and indices within k?"

Now you need "is there a nearby value in range", not just equality — a TreeSet with floor/ceiling over a sliding window. O(n log k). See 02 — Collections §3.