Leetcode 217 - Contains Duplicate

Table of contents

Problem

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.

Example 1:

Input: nums = [1,2,3,1]
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

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Explanation/Approach

This problem checks if any value in the array appears more than once. We can use a hash set to solve this efficiently.

• Hash Set Approach: Iterate over the array and add elements to a hash set. If an element is already in the set, it means the array has a duplicate.

Solution: Hash Set Approach

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()  # Initialize an empty set

        # Iterate over the elements of the array
        for num in nums:
            # Check if the number is already in the set
            if num in seen:
                return True
            # Add the number to the set
            seen.add(num)

        # No duplicates found
        return False

Time and Memory Complexity

The time complexity is O(n), where n is the number of elements in the array, as we traverse the array once. The space complexity is O(n) in the worst case, when there are no duplicates, as we store each element in the set.

Explanation

The solution uses a hash set to keep track of the elements seen so far. For each element in the array, it checks if the element is already in the set. If it is, the function returns True, indicating a duplicate. If not, the element is added to the set. If the function completes the iteration without finding any duplicates, it returns False.