LeetCode 217: Contains Duplicate Solution in Python Explained

Problem Statement

In LeetCode 217: Contains Duplicate, you’re given:

• nums: An array of integers.
• Your task is to return true if any value appears at least twice, false if every element is distinct.

This is a simple yet fundamental problem, differing from combination generation in LeetCode 216: Combination Sum III, focusing instead on detecting repetition in an array.

Constraints

• 1 ≤ nums.length ≤ 10⁵.
• -10⁹ ≤ nums[i] ≤ 10⁹.

Examples

Let’s see some cases:

Copy codeInput: nums = [1,2,3,1]
Output: true
Explanation: 1 appears twice, so there’s a duplicate.

Copy codeInput: nums = [1,2,3,4]
Output: false
Explanation: All elements are unique, no duplicates.

Copy codeInput: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: Multiple duplicates (1, 2, 3, 4 appear more than once).

These examples show we’re checking for any repeated values.

Understanding the Problem

How do we solve LeetCode 217: Contains Duplicate in Python? For nums = [1,2,3,1], we need to detect that 1 appears twice, returning true. A naive approach might compare every pair (O(n²)), but that’s inefficient. This isn’t a kth largest element problem like LeetCode 215: Kth Largest Element in an Array; it’s about quickly identifying duplicates. We’ll use: 1. Hash Set: O(n) time, O(n) space—our best solution. 2. Sorting: O(n log n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Hash Set Approach

Explanation

The Hash Set approach uses a set to track seen numbers:

• Iterate through the array.
• For each number, check if it’s in the set:
• If yes, we’ve found a duplicate, return true.
• If no, add it to the set and continue.
• If the loop completes, return false.

This runs in O(n) time (single pass with O(1) set operations) and O(n) space (storing up to n elements), making it fast and intuitive—our best solution.

For [1,2,3,1], it detects the second 1 immediately.

Step-by-Step Example

Example 1: nums = [1,2,3,1]

Goal: Return true.

• Step 1: Initialize.
• seen = set() (empty set).
• Step 2: Iterate through nums.
• num = 1: Not in seen, add 1, seen = {1{.
• num = 2: Not in seen, add 2, seen = {1,2{.
• num = 3: Not in seen, add 3, seen = {1,2,3{.
• num = 1: In seen, return true.
• Output: true.

Example 2: nums = [1,2,3,4]

Goal: Return false.

• Step 1: seen = set().
• Step 2:
• num = 1: Add 1, seen = {1{.
• num = 2: Add 2, seen = {1,2{.
• num = 3: Add 3, seen = {1,2,3{.
• num = 4: Add 4, seen = {1,2,3,4{.
• Step 3: No duplicates, return false.
• Output: false.

How the Code Works (Hash Set) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef containsDuplicate(nums: list[int]) -> bool:
    # Line 1: Initialize hash set
    seen = set()
    # Empty set to track numbers (e.g., set())

    # Line 2: Iterate through array
    for num in nums:
        # Process each element (e.g., num=1)
        if num in seen:
            # Check for duplicate (e.g., 1 in {1,2,3{)
            return True
            # Duplicate found (e.g., true)
        seen.add(num)
        # Add to set (e.g., seen={1{)

    # Line 3: No duplicates found
    return False
    # All unique (e.g., false)

This solution is concise and leverages Python’s set efficiency.

Alternative: Sorting Approach

Explanation

The Sorting approach sorts the array first:

• Sort nums in ascending order.
• Iterate through adjacent pairs:
• If any two consecutive elements are equal, return true.
• If no duplicates are found, return false.

It’s O(n log n) time (sorting) and O(1) space (in-place sorting), trading time for simplicity.

Step-by-Step Example

For [1,2,3,1]:

• Sort: [1,1,2,3].
• Check: 1==1, return true.
• Output: true.

For [1,2,3,4]:

• Sort: [1,2,3,4].
• Check: No adjacent equals, return false.
• Output: false.

How the Code Works (Sorting)

Copy codedef containsDuplicateSort(nums: list[int]) -> bool:
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            return True
    return False

Complexity

• Hash Set:
• Time: O(n) – single pass with O(1) set lookups.
• Space: O(n) – set stores all elements.
• Sorting:
• Time: O(n log n) – sorting time.
• Space: O(1) – in-place sorting.

Efficiency Notes

Hash Set is our best solution with O(n) time and straightforward logic, ideal for this problem. Sorting is slower but uses less space, suitable if memory is a constraint.

Key Insights

• Set: Fast lookups.
• Sorting: Adjacent comparison.
• Duplicates: Any repetition counts.

Additional Example

For [7,4,6,4,9,1]:

• Hash Set: Detects 4, true.
• Sorting: [1,4,4,6,7,9], detects 4, true.

Edge Cases

• Single element: [1], false.
• Two equal: [1,1], true.
• Empty (not per constraints): Assume false.

Both handle these well.

Final Thoughts

LeetCode 217: Contains Duplicate in Python is a foundational array problem. Hash Set excels in speed and clarity, while Sorting offers a space-efficient alternative. Want more? Try LeetCode 219: Contains Duplicate II or LeetCode 349: Intersection of Two Arrays. Test your skills—Solve LeetCode 217 on LeetCode with [1,2,3,1] (expecting true)—spot those duplicates today!