LeetCode Solutions Blog

Contains Duplicate

Number: 217

Difficulty: Easy

Paid? No

Problem Description

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.

Key Insights

A hash set can be used to keep track of seen numbers.
Iterating once through the array provides an efficient solution.
If a number is already in the set, a duplicate is found.
Alternative approaches like sorting have a higher time complexity (O(n log n)).

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

The solution uses a hash set to track the numbers seen while iterating through the array. For each number in the array:

Check if it exists in the hash set.
If it does, return true immediately as a duplicate is found.
Otherwise, add the number to the hash set. If the iteration completes without finding any duplicates, return false. This approach efficiently determines if any duplicates exist in a single pass.

Code Solutions

# Function to determine if there are any duplicates in the list.
def contains_duplicate(nums):
    # Create a set to keep track of numbers seen so far.
    seen = set()
    # Iterate over each number in the list.
    for num in nums:
        # If num is already in seen, duplicate found.
        if num in seen:
            return True
        # Add num to the set.
        seen.add(num)
    # No duplicates found.
    return False

# Example usage:
if __name__ == "__main__":
    nums = [1, 2, 3, 1]
    print(contains_duplicate(nums))  # Expected output: True