Problem Description

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

My Idea

My initial idea was to iterate over the array and store key, value pairs for every element and its frequency. In the end i convert the frequencies to a set and add the value 1 to it. The results comes from checking the length of the set: if it’s more than 1 we return True. This idea has a time and space complexity of O(n). My improved idea is to simply convert the list to a set and check if its length has changed. If it has then the list contained duplicates. The final version is the same as the improved, but reduced to a single line of code. Both improved versions retain the O(n) time complexity, but are mostly faster in real world use.

My solution

# Same as the Fast solution, but in one line of code
def containsDuplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

# Faster solution with O(n) time complexity and space complexity
def containsDuplicateFast(nums: list[int]) -> bool:
    if len(set(nums))<len(nums):
        return True
    return False
# Initial idea with O(n) time and space complexity
def containsDuplicateInital(nums: list[int]) -> bool:
    if nums == [] or len(nums)==1:
        return False
    freqs=dict()
    for n in nums:
        if n not in freqs:
            freqs[n]=1
        else:
            freqs[n]+=1
    x=set(freqs.values())
    x.add(1)
    if len(x)>1:
        return True

    return False