Problem Statement in English

You’re given a list nums. Your task is to return true if any element has duplicates in the list, and false otherwise.

Approach

We iterate over the list, and add any elements we haven’t already seen before to a set. If the element already exists in the set, then this element is a duplicate, and we return true. Otherwise, if we made it to the end of the list without returning true, return false.

Solution in Python

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        s = set()

        for i in nums:
            if i in s:
                return True
            else:
                s.add(i)

        return False

Complexity

  • Time: O(n)O(n)
    Since we iterate over the array to check each one or add it to the set.

  • Space: O(n)O(n)
    Since we use a set that stores atmost nn elements.

And we are done.