Problem

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1:

Input: nums = [1, 2, 3, 3]

Output: true

Example 2:

Input: nums = [1, 2, 3, 4]

Output: false

Solution

Naive Looping

Naive solution to loop through the list and checking the dictionary on each loop. Breaking when there is a duplicate with expected value True.

• time complexity: O(n)
• space complexity: O(n)

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        result = False
        checkDict = {}
        for i in nums:
            if checkDict.get(i) == None:
                checkDict[i] = i
            else: 
                result = True
                break
        return result

Relying on Set Data Structure

Building set data structure to detect duplicates:

• time complexity: O(n)
  • we iterate through the original array
• space complexity: O(n)
  • we create a new set

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hashset = set()
        
        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

Comparing the length of original array and set created from the original array:

• time complexity: O(n)
  • we create a new set, so O(n)
• space complexity: O(n)
  • we create a new set, so O(n) worst case

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