217. Contains Duplicates

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.

Solution

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        found = set()
        for num in nums:
            if num in found:
                return True
            else:
                found.add(num)
        return False

Time Complexity: O(n)

Space Complexity: O(n)

Explanation

The idea is to linearly go through the input "nums" and basically remember everything we've seen in a constant-access data structure.

By doing so, we're able to check, efficiently, if we've encountered a particular entry in nums before.

Alternatively, if linear space was an issue and you could afford to sacrifice some time complexity: Sorting the nums list and comparing adjacent values would also work. This would simply be O(nlgn) time and O(1) space.