Contains Duplicate

The problem description can be found in LeetCode.

Approach

A naive approach would consist of checking all possible pairs, which would require $O(n^2)$ time.

Another possibility would consist of sorting the input array and then make a linear search to look at two consecutive elements to find out if a duplicate is present. This would require $O(nlog(n))$ time for sorting and $O(n)$ for the linear search, hence the total time complexity would be $O(nlog(n))$.

As usual, we can improve the overall time complexity by using an auxiliary data structures to keep track of some intermediate results. In this case, we can use a Set for a quick lookup of duplicated elements.

Solution

from typing import List


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

        for num in nums:
            if num in seen:
                return True

            seen.add(num)

        return False

The same algorithm can be implemented in a single line. However, this would create a set every time. So for inputs that contain duplicates at the very beginning, this algorithm would be slower compared to the first one, but the space and time complexity would remain the same.

from typing import List


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

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the nums list.