🧑‍🤝‍🧑217. Contains Duplicate

Easy | Grind 75 | November 2nd Wednesday, 2022

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.

Constraints:

• 1 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

Example 1

Input: nums = [1,2,3,1]
Output: trueInput: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Example 2

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

Example 3

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

SOLUTION

One way to solve this question is to iterate the elements while keeping a tracker of whether we saw the elements before. We will use a dictionary to track the elements. Every time we iterate over an element, we check if the dictionary contains the element. We return false if the element is present in the dictionary.

    def containsDuplicate(self, nums: List[int]) -> bool:
        # track of elements seen 
        seen = {} 
        
        for element in nums: 
            if element in seen: 
                return True
            
            # if not seen, add to seen
            seen[element] = 1
            
        # code reaches here only if there are no duplicates
        return False

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the list. In the worst case(no duplicates), we have to iterate n times.

SPACE: O(n) where n is the length of the list. In the worst case(no duplicates), we have to store every single element in the dictionary.