A nightly intake job receives warehouse scan IDs. If any ID appears twice, the file is a double-count and on-hand stock will drift. The first version nested a scan: for each i, every j > i. A few hundred IDs on a quiet dock returned instantly. Two million IDs from a holiday weekend were still comparing when the job’s lock expired.

Contains Duplicate asks whether any value appears at least twice. An array already gives a[i] for free. Nested comparison uses that and still pays O(n²). Sorting would make adjacent equals a linear check, but sorting permutes an array you were not asked to reorder.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about remembering what we have already seen so a repeat is a lookup, not a restart.

The problem

Given an int[] nums, return true if any value occurs more than once, and false if every value is unique.

nums = [41, 8, 41, 17]   →  true    41 appears twice
nums = [9, 4, 6, 2]      →  false
nums = [3, 3]            →  true

Note: Sort, then walk neighbors, is a legal middle path. It is not the usual interview answer: the prompt did not ask you to permute the input, and a set answers in one pass without that rewrite.

Nested comparison is the honest brute force

Every unordered pair is visited once. Correct. Quadratic.

boolean containsDuplicateNested(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;
}

At n = 20 this is a rounding error. At n in the hundreds of thousands you paid a nested scan for a question a set answers in expected constant time per index: have I already seen this value?

One pass: return on the first collision

Walk left to right. Before you look at nums[i], the set holds every earlier value.

  • If nums[i] is already a member, you are done: return true.
  • Otherwise add it and continue.

You never restart a scan from index 0. You never sort. You stop at the first collision instead of proving uniqueness the long way.

nums = [41, 8, 41, 17]

i=0  value=41   set {}         miss, add 41
i=1  value=8    set {41}       miss, add 8
i=2  value=41   set {41, 8}    hit, return true

The Java is that walk. Set.add returns false when the value was already present, so the collision test is the add itself:

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

Time is expected O(n) — one pass, one expected-O(1) add per index. Space is O(n) for the set. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Contains-then-add is the same idea with two calls. Either order is safe here: a duplicate is a duplicate whether you test membership first or let add refuse the insert. Empty input never enters the loop and returns false — nothing repeated.

What interviewers usually poke next

  • Empty array. No value appears twice. Return false. Do not invent a special case unless they ask.
  • All unique. The set grows to n, you fall off the end, return false. Say the space bill out loud.
  • Return the duplicate value, not a boolean. On collision, return n instead of true. If several values repeat, ask which one they want — first seen twice, or any.
  • Memory-tight. Sort in place, then compare neighbors. O(1) extra space if mutation is allowed, O(n log n) time, and you should say why the set is still the default when they did not ask you to reorder.

You are done with this problem when you can say, out loud, why the nested scan is correct, why sorting is legal but permutes the input, and why the set returns on the first collision instead of finishing the pass.