Contains DuplicateEasy

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

Examples

Input: nums = [1,2,3,1] → Output: true

Input: nums = [1,2,3,4] → Output: false

Approach

Three ways to think about this, in increasing order of efficiency: compare every pair (O(n²)); sort first so duplicates become adjacent, then scan once (O(n log n)); or track everything you've seen in a Set as you go, so each check is O(1) (O(n) overall). The Set approach is the one worth internalizing — 'have I seen this before?' is one of the most common questions in array problems, and a Set answers it in constant time.

Complexity — best & worst case

Sort approach — time O(n log n), same for best and worst case (sorting dominates)

Optimal (Set) — time O(n) worst case (no duplicates, must scan everything), O(1) best case (first two elements duplicate)

Optimal (Set) — space O(n)

Code

// Given an array of integers, return true if any value appears at
// least twice, false if every element is distinct.

// --- Brute force: compare every pair ---
function containsDuplicateBrute(nums) {
  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;
}

// --- Better: sort first, then check neighbors ---
function containsDuplicateSort(nums) {
  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;
}

// --- Optimal: a Set remembers what's been seen, O(1) lookup ---
function containsDuplicate(nums) {
  const seen = new Set();
  for (const num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

// --- Example Usage ---
console.log(containsDuplicate([1, 2, 3, 1])); // true
console.log(containsDuplicate([1, 2, 3, 4])); // false
console.log(containsDuplicateSort([1, 2, 3, 1])); // true
console.log(containsDuplicateBrute([1, 2, 3, 4])); // false