Contains Duplicate

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

Example

nums = [1, 2, 3, 1]                 ->  true
nums = [1, 2, 3, 4]                 ->  false
nums = [1, 1, 1, 3, 3, 4, 3, 2, 4]  ->  true

The pattern: sort first, then scan

Many questions are hard on a jumbled array and easy on a sorted one. Sorting puts related values next to each other: equal values become neighbours, the closest pair of numbers sits side by side, and intervals line up by start time so overlaps are adjacent. After an O(n log n) sort, a single O(n) scan comparing neighbours (or tracking a running value) finishes the job.

The cost to remember: sorting is O(n log n) and either modifies the input or needs a copy. When a hash map can answer the question in O(n), it's faster — but sorting needs no extra memory if you may reorder the input, and it's the only easy route when the question is about order (closest, overlapping, the h-th largest). The questions in this chapter all follow this shape.

1. Brute force: compare every pair

1function containsDuplicate(nums) {2  for (let i = 0; i < nums.length; i++) {3    for (let j = i + 1; j < nums.length; j++) {4      if (nums[i] === nums[j]) return true;5    }6  }7  return false;8}

Time O(n²), space O(1). About n²/2 comparisons — too slow for 10⁵ values.

2. Sort, then compare neighbours

1function containsDuplicate(nums) {2  const sorted = [...nums].sort((a, b) => a - b);   // equal values end up side by side3  for (let i = 1; i < sorted.length; i++) {4    if (sorted[i] === sorted[i - 1]) return true;   // a value equal to its neighbour5  }6  return false;7}

Time O(n log n), space O(n) for the copy — or O(1) extra if you may sort nums itself.

3. A hash set of values seen

1function containsDuplicate(nums) {2  const seen = new Set();3  for (const x of nums) {4    if (seen.has(x)) return true;                 // seen before: a duplicate5    seen.add(x);6  }7  return false;8}

Time O(n), space O(n). The fastest, at the price of a set as big as the input.

Comparing the approaches

Mention both 2 and 3: the set is faster, sorting saves memory. Interviewers like hearing the trade-off.

Edge cases to test

Variations