Optimize the code · Easy

Speed Up Contains Duplicate

Easy Make it fast Most askedSeen at Amazon, Apple, Adobe

containsDuplicate(nums) returns true if any value appears at least twice in nums, otherwise false.

The version below is correct, and it was fine in tests with ten elements. In production it receives arrays of 100,000 IDs and requests start timing out. Make it fast enough that every case, including the 100,000-element ones, finishes inside the time budget. The answers must not change.

Example 1

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

Example 2

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

Constraints

0 <= nums.length <= 100000
-10^9 <= nums[i] <= 10^9

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function containsDuplicate(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;
}

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;
}

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

<?php

function containsDuplicate(array $nums): bool
{
    $n = count($nums);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($nums[$i] === $nums[$j]) {
                return true;
            }
        }
    }
    return false;
}

class Solution {
    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;
    }
}

Hints

Hint 1

How many pairs does the nested loop compare for n = 100,000?

Hint 2

What data structure answers "have I seen this value before?" in O(1)?

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Why it is slow: the nested loop compares every pair, n(n-1)/2 comparisons. For 100,000 elements that is about 5 billion comparisons, seconds even in a fast runtime, and it grows with the square of the input.

The fix: remember what you have seen in a hash set. Each element is checked and inserted once, so the work is O(n): about 100,000 set operations instead of 5 billion comparisons. Sorting first and comparing neighbours (O(n log n), O(1) extra space if you may reorder the input) is the other acceptable answer; mention it when memory is tight.

The interview signal is the reasoning: state the current complexity, estimate the work for the real input size, and name the data structure that removes the inner loop.

Optimized solution

function containsDuplicate(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) 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;
}

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

<?php

function containsDuplicate(array $nums): bool
{
    $seen = [];
    foreach ($nums as $x) {
        if (isset($seen[$x])) {
            return true;
        }
        $seen[$x] = true;
    }
    return false;
}

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

Common mistakes

Using array.includes(x) / x in list inside the loop: still O(n^2), just hidden.
Building new Set(nums).size !== nums.length is fine, but cannot stop early on the first duplicate.
Sorting the caller's array in place without saying so.

Follow-up questions

Contains Duplicate II: duplicates at most k indices apart (sliding-window set).
The input does not fit in memory: what would you do? (external sort, or hash-partition to disk)

Speed Up Two Sum · Easy
Speed Up Recursive Fibonacci · Easy
Speed Up the Most Frequent Word · Easy
Speed Up the Active-Customer Join · Easy
Speed Up Range Sum Queries · Medium
Speed Up Longest Consecutive Sequence · Medium