Contains Duplicate

Given an integer array nums, determine if any value appears at least twice in the array. Return true if any value appears at least twice in the array, and return false if every element is distinct.

For example:

• nums = [1,2,3,1] should return true because 1 appears twice.
• nums = [1,2,3,4] should return false because all elements are distinct.
• nums = [1,1,1,3,3,4,3,2,4,2] should return true because 1, 3, 4, and 2 all appear multiple times.

What is the most efficient algorithm to solve this problem?

## Contains Duplicate

### Problem Description

Given an integer array `nums`, determine if any value appears at least twice in the array. Return `true` if a duplicate is found, and `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

### Brute Force Solution

A straightforward approach is to iterate through the array and, for each element, check if it exists later in the array. This involves nested loops.

```python
def contains_duplicate_brute_force(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Optimal Solution

Using a hash set (or just a set in Python) can significantly improve performance. Iterate through the array and add each element to the set. If an element is already in the set, it means a duplicate has been found.

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

Big(O) Run-time Analysis

Brute Force Solution:

• Time Complexity: O(n^2) because of the nested loops. For each element, we compare it with every other element in the array.

Optimal Solution:

• Time Complexity: O(n) because we iterate through the array once. Set lookups and insertions take O(1) time on average.

Big(O) Space Usage Analysis

Brute Force Solution:

• Space Complexity: O(1) because it uses a constant amount of extra space.

Optimal Solution:

• Space Complexity: O(n) in the worst case, as the seen set might store all the elements of the array if there are no duplicates.

Edge Cases and Considerations

1. Empty Array: If the input array is empty, the function should return false because there can be no duplicates.
2. Array with One Element: Similarly, if the array has only one element, there are no duplicates, so return false.
3. Large Input: For very large arrays, the optimal solution using a set is crucial to avoid quadratic time complexity.
4. Negative Numbers and Zero: The code should handle negative numbers and zero correctly, as these are valid integers.

Here's the implementation that handles the first two edge cases:

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