217. Contains Duplicate

Description

See https://leetcode.com/problems/contains-duplicate/

Solutions

There are numerous solutions to this problem. Here are a few.

Solution 1

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

Space O(N), Time O(N) - from creating the set

Solution 2

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        cache = defaultdict(int)
        for i in nums:
            if i in cache:
                return True
            else:
                cache[i] = i
        return False

Space O(N), Time O(N)

Solution 3

This would be the slowest solution as it has the overhead of sorting the list.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        sorted_list = sorted(nums)
        for i in range(len(sorted_list) - 1):
            if sorted_list[i] == sorted_list[i+1]:
                return True
        return False

Space O(N), Time O(N log N) - Time complexity for sort. See: https://wiki.python.org/moin/TimeComplexity