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: true

  • Example 2:

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

Solution

  • Approach: Utilize a hash set (or hash map) to efficiently track seen elements.

    • Iterate through each number in the input array.
    • For each number, check if it's already present in the hash set.
    • If it is, a duplicate has been found, so return true.
    • If it's not, add the number to the hash set.
    • If the loop completes without finding any duplicates, return false.

  • Why a hash set?:

    • Insertion and lookup operations in a hash set typically take O(1) average time complexity.
    • This makes it much more efficient than sorting the array (O(N log N)) or using nested loops (O(N^2)).

  • Time Complexity: O(N) on average, where N is the number of elements in nums. In the worst case (all elements unique), we iterate through all N elements and perform N insertions.

  • Space Complexity: O(N) on average, as in the worst case, all elements are unique and stored in the hash set.

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