217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Source

Code

In [2]:

def contains_duplicate(nums):
    """Using set()
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    my_set = set()
    for n in nums:
        if n in my_set:
            return True
        my_set.add(n)
    return False

In [3]:

def contains_duplicate(nums):
    """variation of above solution"""
    return len(nums) != len(set(nums))

Check

In [5]:

nums = [1,2,3,1]
contains_duplicate(nums)

Out[5]:

True

In [6]:

nums = [1,2,3,4]
contains_duplicate(nums)

Out[6]:

False

In [7]:

nums = [1,1,1,3,3,4,3,2,4,2]
contains_duplicate(nums)

Out[7]:

True

Follow up:

Can you solve it with O(1) Space Complexity (i.e. constant memory)?

In [9]:

def contains_duplicate(nums):
    """using sort, and check consecutive items
    Time Complexity: O(nlogn)
    Space Complexity: O(1)
    """
    if len(nums) < 2:
        return False
    nums.sort()
    for i, num in enumerate(nums[:-1]):
        if num == nums[i+1]:
            return True
    return False

In [10]:

nums = [1,2,3,1]
contains_duplicate(nums)

Out[10]:

True

In [11]:

nums = [1,2,3,4]
contains_duplicate(nums)

Out[11]:

False

In [12]:

nums = [1,1,1,3,3,4,3,2,4,2]
contains_duplicate(nums)

Out[12]:

True