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 O(n) time complexity. If we have to do this for every item in the array, we’ll have an O(n^2) time complexity.
• A better solution would be to use a set(). Since sets are hashed, checking if an item is in the set is O(1), rather than O(n).
  • This simplifies our entire problem into O(n), rather than O(n^2).
  • When creating a set, we sacrifice a small space complexity, though (O(n)).

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

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