#6 · Arrays & Hashing

Contains Duplicate

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

EasyLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Hash set

Stores each value once and answers "have I seen this?" in average O(1). Inserting a value that is already present is how duplicates reveal themselves.

Memory layout

A table of buckets or open-addressed slots holding keys. Probes scatter across memory, so each lookup is a likely cache miss; the table also keeps spare capacity (load factor) beyond n entries.

Operation	Cost
insert / contains	O(1) average, O(n) worst
space	O(n) plus load-factor slack

Sorted array / direct-address bitmap

Sorting makes equal values adjacent, so duplicates need only a neighbour comparison. When values fall in a small range, a flat array indexed by value replaces hashing entirely.

Memory layout

Both are contiguous. A scan over a sorted array is prefetch-friendly. A bitmap costs one byte (or bit) per possible value, independent of n.

Operation	Cost
sort	O(n log n)
neighbour scan	O(n)
bitmap lookup / set	O(1) worst case, O(range) space

Why it fits

Duplicate detection is a membership question: "is this value already present?". A hash set answers it in O(1) per element, so a single pass suffices.
The answer can be returned the moment the first repeat is seen, so the average cost is often well below n.
The pigeonhole principle gives a free shortcut: if there are more elements than distinct possible values, a duplicate is guaranteed, with no scanning at all.

Why alternatives degrade

Nested loops:: O(n²) comparisons; about 5 × 10⁹ for n = 10⁵.
Sorting:: O(n log n) and it modifies or copies the input; slower than hashing when n is large, though it needs no extra hash memory if sorted in place.
Balanced tree set:: O(log n) per operation with pointer-chasing nodes; strictly worse than a hash set unless order is needed.

Four approaches, from naive to production

1 · beginner

Compare every pair

time O(n²)space O(1)

For each element, scan all later elements and return true on the first equal pair.

bool containsDuplicate(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}

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

def contains_duplicate(nums: list[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]: return True
    return False

function containsDuplicate(nums: number[]): boolean {
  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;
}

Flaws & bottlenecks

Quadratic: about n²/2 comparisons, so ~5 × 10⁹ for n = 10⁵, which is a timeout.
Worst case (all distinct) does the maximum work and finds nothing.
No information is reused between iterations.

Interviewer cross-questions

Can you do better than O(n²)?

Say: Yes. Duplicate detection only needs to know whether a value was seen before. A hash set gives that in O(1), so one pass is O(n) time at the cost of O(n) space. Alternatively sort first (O(n log n)) so duplicates become adjacent.

When is the brute force the right answer?

Say: For tiny arrays (a handful of elements) or when memory is strictly forbidden and mutation of the input is not allowed. It is allocation-free and cache-friendly, and for n < ~16 it can beat hashing.

What is the best case?

Say: O(1) if the first two elements are equal, and the worst case is O(n²) when all elements are distinct.

2 · intermediate

Sort, then compare neighbours

time O(n log n)space O(n) copy (O(1) if you may sort in place)

Sort a copy of the array. Any duplicate values end up next to each other, so one linear scan finds them.

bool containsDuplicate(vector<int>& nums) {
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    for (size_t i = 1; i < sorted.size(); i++) {
        if (sorted[i] == sorted[i - 1]) return true;
    }
    return false;
}

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

def contains_duplicate(nums: list[int]) -> bool:
    ordered = sorted(nums)
    for i in range(1, len(ordered)):
        if ordered[i] == ordered[i - 1]: return True
    return False

function containsDuplicate(nums: number[]): boolean {
  const sorted = [...nums].sort((a, b) => a - b);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

Flaws & bottlenecks

O(n log n) sorting dominates; it does far more ordering work than the problem needs.
Sorting a copy costs O(n) memory; sorting in place mutates the caller's array.
Cannot answer early: the whole array must be sorted before the first comparison.

Interviewer cross-questions

Why is sorting enough?

Say: After sorting, equal values form contiguous runs. So if any duplicate exists, some adjacent pair is equal. Checking only n − 1 neighbour pairs is therefore both necessary and sufficient.

Can you avoid the extra memory?

Say: Yes: sort in place (heap sort gives O(1) extra space and O(n log n) time). The cost is mutating the input, which is only acceptable if the caller does not need the original order.

Why pass a comparator to sort?

Say: Default sort in JavaScript compares as strings, so 10 sorts before 9. A numeric comparator (a − b) is required for correct order. (Python, Java and C++ sort numbers numerically by default.)

3 · advanced

Hash set, single pass

time O(n)space O(n)

Walk the array once, keeping a set of values seen so far. If the current value is already in the set, return true.

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

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

def contains_duplicate(nums: list[int]) -> bool:
    seen: set[int] = set()
    for x in nums:
        if x in seen: return True
        seen.add(x)
    return False

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Flaws & bottlenecks

O(n) extra memory in the worst case (all distinct): the set may hold every element.
Hash costs: hashing, collisions, resize and rehash; the constant is much larger than a plain array scan.
Average-case O(1): adversarial or poorly hashed keys can degrade a lookup to O(n).

Interviewer cross-questions

What if memory is limited or the data is huge?

Say: Sort externally (merge sort on disk) and scan neighbours, or hash-partition the data into buckets that fit in memory and check each bucket independently. A Bloom filter can pre-screen candidates cheaply but gives false positives, so confirmed hits still need an exact check.

Can you make it early-exit friendlier?

Say: It already returns at the first repeat. Cost is proportional to the position of the first duplicate, not to n.

Is a hash set always O(1)?

Say: Only on average. Worst case O(n) per operation with many collisions. Production hash tables mitigate that with randomized seeds (anti hash-flooding) or tree-ified buckets (Java HashMap).

4 · expert

Range-aware: pigeonhole + bitmap

time O(n) (O(n + range) with the bitmap)space O(range) bitmap, or O(n) with the fallback

One cheap pass finds min and max. If the range is smaller than n, a duplicate is guaranteed. If it is small, use a flat byte table indexed by value − min. Otherwise fall back to a hash set.

bool containsDuplicate(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return false;
    int lo = nums[0], hi = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < lo) lo = nums[i];
        else if (nums[i] > hi) hi = nums[i];
    }
    long long range = (long long)hi - lo + 1;
    if (range < n) return true;
    if (range <= (1 << 20)) {
        vector<char> bits(range, 0);
        for (int i = 0; i < n; i++) {
            long long k = (long long)nums[i] - lo;
            if (bits[k] == 1) return true;
            bits[k] = 1;
        }
        return false;
    }
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

public boolean containsDuplicate(int[] nums) {
    int n = nums.length;
    if (n < 2) return false;
    int lo = nums[0], hi = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < lo) lo = nums[i];
        else if (nums[i] > hi) hi = nums[i];
    }
    long range = (long) hi - lo + 1;
    if (range < n) return true;
    if (range <= (1 << 20)) {
        boolean[] bits = new boolean[(int) range];
        for (int i = 0; i < n; i++) {
            int k = nums[i] - lo;
            if (bits[k]) return true;
            bits[k] = true;
        }
        return false;
    }
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (seen.contains(x)) return true;
        seen.add(x);
    }
    return false;
}

def contains_duplicate(nums: list[int]) -> bool:
    n = len(nums)
    if n < 2: return False
    lo = hi = nums[0]
    for i in range(1, n):
        if nums[i] < lo: lo = nums[i]
        elif nums[i] > hi: hi = nums[i]
    span = hi - lo + 1
    if span < n: return True
    if span <= 1 << 20:
        bits = bytearray(span)
        for i in range(n):
            k = nums[i] - lo
            if bits[k] == 1: return True
            bits[k] = 1
        return False
    seen: set[int] = set()
    for x in nums:
        if x in seen: return True
        seen.add(x)
    return False

function containsDuplicate(nums: number[]): boolean {
  const n = nums.length;
  if (n < 2) return false;
  let lo = nums[0], hi = nums[0];
  for (let i = 1; i < n; i++) {
    if (nums[i] < lo) lo = nums[i];
    else if (nums[i] > hi) hi = nums[i];
  }
  const range = hi - lo + 1;
  if (range < n) return true;
  if (range <= 1 << 20) {
    const bits = new Uint8Array(range);
    for (let i = 0; i < n; i++) {
      const k = nums[i] - lo;
      if (bits[k] === 1) return true;
      bits[k] = 1;
    }
    return false;
  }
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Flaws & bottlenecks

More code and three code paths to test, for a gain that exists only when the value range is small.
The bitmap costs O(range) memory: wasteful when n is small but values are widely spread (hence the 2²⁰ cap).
hi − lo + 1 can overflow in fixed-width integer languages; it must be computed in a wider type.

Interviewer cross-questions

Why does range < n guarantee a duplicate?

Say: Pigeonhole principle: there are only `range` distinct integers between min and max, and n > range items to place in them, so at least two items share a value. It costs one pass to find min and max and then returns without reading any element a second time.

How would you shrink the bitmap?

Say: Use one bit per value instead of one byte (a bitset), an 8× saving. For 2²⁰ values that is 128 KB, which fits in L2 cache, so lookups stay fast.

What overflow risks exist?

Say: hi − lo + 1 can exceed the integer width (e.g. lo = −2³¹, hi = 2³¹ − 1 in 32-bit ints). Compute it in 64-bit before comparing to n or to the cap, and before casting to an allocation size.

Synchronized code walkthrough

Showing: Compare every pair — shares the player above; click any step to jump.

bool containsDuplicate(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}

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

def contains_duplicate(nums: list[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]: return True
    return False

function containsDuplicate(nums: number[]): boolean {
  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;
}

bool containsDuplicate(vector<int>& nums) {
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    for (size_t i = 1; i < sorted.size(); i++) {
        if (sorted[i] == sorted[i - 1]) return true;
    }
    return false;
}

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

def contains_duplicate(nums: list[int]) -> bool:
    ordered = sorted(nums)
    for i in range(1, len(ordered)):
        if ordered[i] == ordered[i - 1]: return True
    return False

function containsDuplicate(nums: number[]): boolean {
  const sorted = [...nums].sort((a, b) => a - b);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

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

def contains_duplicate(nums: list[int]) -> bool:
    seen: set[int] = set()
    for x in nums:
        if x in seen: return True
        seen.add(x)
    return False

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

bool containsDuplicate(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return false;
    int lo = nums[0], hi = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < lo) lo = nums[i];
        else if (nums[i] > hi) hi = nums[i];
    }
    long long range = (long long)hi - lo + 1;
    if (range < n) return true;
    if (range <= (1 << 20)) {
        vector<char> bits(range, 0);
        for (int i = 0; i < n; i++) {
            long long k = (long long)nums[i] - lo;
            if (bits[k] == 1) return true;
            bits[k] = 1;
        }
        return false;
    }
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

public boolean containsDuplicate(int[] nums) {
    int n = nums.length;
    if (n < 2) return false;
    int lo = nums[0], hi = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < lo) lo = nums[i];
        else if (nums[i] > hi) hi = nums[i];
    }
    long range = (long) hi - lo + 1;
    if (range < n) return true;
    if (range <= (1 << 20)) {
        boolean[] bits = new boolean[(int) range];
        for (int i = 0; i < n; i++) {
            int k = nums[i] - lo;
            if (bits[k]) return true;
            bits[k] = true;
        }
        return false;
    }
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (seen.contains(x)) return true;
        seen.add(x);
    }
    return false;
}

def contains_duplicate(nums: list[int]) -> bool:
    n = len(nums)
    if n < 2: return False
    lo = hi = nums[0]
    for i in range(1, n):
        if nums[i] < lo: lo = nums[i]
        elif nums[i] > hi: hi = nums[i]
    span = hi - lo + 1
    if span < n: return True
    if span <= 1 << 20:
        bits = bytearray(span)
        for i in range(n):
            k = nums[i] - lo
            if bits[k] == 1: return True
            bits[k] = 1
        return False
    seen: set[int] = set()
    for x in nums:
        if x in seen: return True
        seen.add(x)
    return False

function containsDuplicate(nums: number[]): boolean {
  const n = nums.length;
  if (n < 2) return false;
  let lo = nums[0], hi = nums[0];
  for (let i = 1; i < n; i++) {
    if (nums[i] < lo) lo = nums[i];
    else if (nums[i] > hi) hi = nums[i];
  }
  const range = hi - lo + 1;
  if (range < n) return true;
  if (range <= 1 << 20) {
    const bits = new Uint8Array(range);
    for (let i = 0; i < n; i++) {
      const k = nums[i] - lo;
      if (bits[k] === 1) return true;
      bits[k] = 1;
    }
    return false;
  }
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}