Leetcode: 217. Contains Duplicate

• Pattern: Searching in Array
• Pattern: Problem's constraints disallow \(O(n^2)\) solutions

Given an array of integers, determine if there are any duplicate integers. We can use a set to store the distinct numbers of the array. If the length of the set is equal to \(n\), then all numbers are distinct and the answer is \(false\). Otherwise, the answer is \(true\) since there is at least one duplicate integer in the array. The time and space complexity is \(O(n)\) as all numbers to the set.

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

Alternatively, the problem can be solved as a search problem. For each integer \(i\), search \(a[i]\) in \(a[0...(i-1)]\) returning \(true\) if it is found. If the search failed for all integers, then the answer is \(false\) since all integers are distinct. A linear search does not consume extra memory, but it is too slow for the problem's constraints. We can sort the array what makes the search trivial as \(a[i]\) needs to be only checked against \(a[i-1]\) to determine if it is duplicated or not. The time complexity of this solution is \(O(n \log n)\). Other approach is to use extra memory: Binary Search Tree or Hash Table. The former supports insertion and look up in \(O(\log n)\) resulting in the same time complexity as sorting the array, while the latter supports the same operation in \(O(1)\) resulting in same time complexity as counting the number of distinct integers.

• Interview preparation: V