Contains Duplicate

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

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

Solution

• Looking at this problem, my naive solution would be to simply do something like if num in nums: return True.
  • However, looking up items in array/list is time complexity. If we have to do this for every item in the array, we’ll have an time complexity.
• A better solution would be to use a set(). Since sets are hashed, checking if an item is in the set is , rather than .
  • This simplifies our entire problem into , rather than .
  • When creating a set, we sacrifice a small space complexity, though ().

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        # time complexity: O(n) * O(1) = O(n)
        # space complexity: O(n)
        num_set = set()
 
        for num in nums:
            if num in num_set:
                return True
 
            num_set.add(num)
 
        return False

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───