Problem Statement

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.

Additional information

• Assume that the array will have at most 10,000 elements.
• The elements in the array are integers.
• The function should handle edge cases such as empty lists and single element lists.

Example 1:

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

Output: true

Example 2:

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

Output: false

Brute Force

Intuition

We can check every pair of different elements in the array and return true if any pair has equal values.
This is the most intuitive approach because it directly compares all possible pairs, but it is also the least efficient since it examines every combination.

Algorithm

1. Iterate through the array using two nested loops to check all possible pairs of distinct indices.
2. If any pair of elements has the same value, return true.
3. If all pairs are checked and no duplicates are found, return false.

def contains_duplicate(nums: list[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: We use two nested loops, comparing every element with every other element.

• Space complexity: O(1)

• Reason: We do not store any extra data structures, just loop variables.

Sorting

Intuition
If we sort the array, then any duplicate values will appear next to each other. Sorting groups identical elements together, so we can simply check adjacent positions to detect duplicates. This reduces the problem to a single linear scan after sorting.

Algorithm

• Sort the array in non-decreasing order.
• Iterate through the array starting from index 1.
• Compare the current element with the previous element.
• If both elements are equal, we have found a duplicate - return true.
• If the loop finishes without detecting equal neighbors, return false.

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

Time & Space Complexity

• Time complexity: O(n log n)

• Reason: The dominant operation is the sorting algorithm. The subsequent pass is O(n).

• Space complexity: O(1) or O(n)

• Reason: Depends on the sorting implementation (e.g., Timsort uses O(n) space).

Hash Set

Intuition
We can use a hash set to efficiently keep track of the values we have already encountered. As we iterate through the array, we check whether the current value is already present in the set. If it is, that means we've seen this value before, so a duplicate exists. Using a hash set allows constant-time lookups.

Algorithm

• Initialize an empty hash set seen_numbers.

• Iterate through each number in the array.

• For each number:

• If it is already in seen_numbers, return true.

• Otherwise, add it to seen_numbers.

• If the loop finishes without finding any duplicates, return false.

def contains_duplicate(nums: list[int]) -> bool:
    seen_numbers = set()
    for num in nums:
        if num in seen_numbers:
            return True
        seen_numbers.add(num)
    return False

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the array once, and set lookups/insertions are O(1) on average.

• Space complexity: O(n)

• Reason: In the worst case (no duplicates), the set stores all n elements.