Leetcode 217 - Contains Duplicate

Problem

Leetcode 217 - Contains Duplicate

Example:

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

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

Approach

Since python has a built-in set data structure, and set is a collection of unique elements, we can convert the list to a set and compare the length of the set and the list or we can for loop through the list and check if the element is already in the set.

Visual representation of the approach:

nums = [1,2,3,3]
set = ()

Since 1 is not in the set, we add it to the set.
set = (1)

Since 2 is not in the set, we add it to the set.
set = (1,2)

Since 3 is not in the set, we add it to the set.
set = (1,2,3)

Since 3 is already in the set, we return true.

Here’s the code implementation of the approach:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # initialize a set
        num_set = set()

        for num in nums:
            if num in num_set:
                return True
            num_set.add(num)
        return False

Time Complexity and Space Complexity

The time complexity is $ O(n) $ since we are iterating through the list once.

The space complexity is $ O(n) $ since we are using a set to store the elements.