Contains Duplicate — LeetCode #217

Contains Duplicate is one of the most asked questions on LeetCode and appears on the Blind 75 list. While it looks simple at first glance, the three solutions illustrate a useful progression in complexity/space tradeoffs.

Problem Statement

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

Input:  [1,2,3,1]         → true
Input:  [1,2,3,4]         → false
Input:  [1,1,1,3,3,4,3]   → true

---

Solutions

1. Brute Force — O(N²) time, O(1) space

Fix one element, search for it in the rest of the array.

def containsDuplicate(nums):
    n = len(nums)
    if n < 2:
        return False
    for i in range(n):
        for j in range(i):
            if nums[i] == nums[j]:
                return True
    return False

2. Sorting — O(N log N) time, O(1) space

Sort so duplicates become adjacent, then a single linear scan suffices.

def containsDuplicate(nums):
    n = len(nums)
    if n < 2:
        return False
    nums.sort()
    for i in range(1, n):
        if nums[i-1] == nums[i]:
            return True
    return False

3. Hash Set — O(N) time, O(N) space

Insert all elements into a set. If the set is smaller than the array, there were duplicates.

def containsDuplicate(nums):
    return len(set(nums)) < len(nums)

One line. The hash set doesn't allow duplicates, so any collision is implicit evidence of a repeat. Space is cheap; time invaluable.

Later.