Domain 1EasyCORE

Contains Duplicate

The problem asks us to determine if there are any duplicate elements in an integer array `nums`. The input is a list of integers, and the output should be a boolean value: `true` if there is at least one duplicate, and `false` if all elements are distinct. The constraints specify that the length of the array can range from 1 to 10^5, and each element can be as large as 10^9 or as small as -10^9.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table

217. Contains Duplicate

Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 56.9%


Problem Breakdown

The problem asks us to determine if there are any duplicate elements in an integer array nums. The input is a list of integers, and the output should be a boolean value: true if there is at least one duplicate, and false if all elements are distinct. The constraints specify that the length of the array can range from 1 to (10^5), and each element can be as large as (10^9) or as small as (-10^9).

Intuition

A brute-force approach would involve checking every pair of elements in the array to see if they are equal. This would have a time complexity of (O(n^2)), which is inefficient given the constraints. The key insight is that we can use a hash table (or set) to track the elements we’ve seen so far, allowing us to detect duplicates in linear time.

Approach

  1. Initialize a Set: Use a set to keep track of unique elements encountered as we iterate through the array.
  2. Iterate Through the Array: For each element in the array:
    • Check if the element is already in the set.
      • If it is, return true because a duplicate has been found.
      • If it is not, add the element to the set.
  3. Return False: If the loop completes without finding any duplicates, return false.

This approach leverages the average (O(1)) time complexity for insertions and lookups in a hash table, resulting in an overall time complexity of (O(n)).

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the number of elements in the array. We iterate through the array once, and each insertion and lookup operation in the set takes average (O(1)) time.
  • Space Complexity: (O(n)), in the worst case, when all elements are unique and stored in the set.

Solution

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Edge Cases Handled

  • Empty Array: The function will correctly return false because there are no elements to compare.
  • Single Element: The function will correctly return false for a single-element array since there can’t be duplicates.
  • All Elements Unique: The function will return false as expected when all elements in the array are distinct.
  • All Elements Duplicates: The function will return true immediately upon encountering the first duplicate element.