217. Contains Duplicate

Problem

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

Example 1:

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

Example 2:

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

Example 3:

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

Solution

A Set only stores unique values, so it is the natural fit here. Walk the array once: if the current number is already in the set, there is a duplicate and we can return early; otherwise add it and continue.

function containsDuplicate(nums: number[]): boolean {
  let mapset = new Set<number>();

  for (let i = 0; i < nums.length; i++) {
    if (mapset.has(nums[i])) {
      return true;
    }

    mapset.add(nums[i]);
  }

  return false;
}

Complexity Analysis

• Set.has and Set.add are O(1) on average
• Worst case (no duplicates) stores every element

Notes

• Alternative: sort the array first and compare neighbors, which is O(n log n) time but O(1) extra space. The set approach is faster and simpler when memory is not a concern.
• Returning early on the first duplicate matters: on arrays with an early duplicate, this does far less work than counting all frequencies.