Blind 75.03 - Contains Duplicate

Contains Duplicate.

Problem description

Taken directly from LeetCode.

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

Constraints:

• 1 <= nums.length <= \(10^5\)
• \(-10^9\) <= nums[i] <= \(10^9\)

Solution type

Hashing

Solution

The best time complexity possible is \(O(n)\), since you need to traverse the entire input array to check whether any one element is a duplicate of another. Hashing gives us a very short solution:

  def containsDuplicate(self, nums: List[int]) -> bool:
      return len(nums) != len(set(nums))

Unordered sets¹ use hashing, meaning it’s \(O(1)\) to add an element to the set². Adding all elements of nums to a set will therefore be \(O(n)\) time total. Sets can only contain one copy of an element; attempting to insert a duplicate element into the set will not modify the set.

This solution creates a set from nums, then checks if the length of the set and the length of nums are the same. Since duplicate elements map to the same single element in the set, there are duplicates iff the lengths are different.

This solution is \(O(n)\) memory. If you want \(O(1)\) memory, you can sort the elements and iterate through the array; duplicates will always be adjacent. This is \(O(n \log n)\) time, which is usually a worse solution - nowadays, memory is cheaper than time.

1. Python sets are unordered.. If you wanted an ordered set for something, one workaround is to insert keys into a dictionary without filling in corresponding values. ↩

2. If you want to be super picky, it’s a little more complicated than this if you start considering hash collisions. For practical purposes it’s \(O(1)\); well-impelemented hash operations shouldn’t noticeably scale with input size except with deliberately engineered adversarial examples. ↩