LeetCode Problem 217: Contains Duplicate
Published: 2024-06-11 10:38:53


### Checking for Duplicate Elements in an Array

Let's solve the problem step-by-step, providing a detailed explanation, code implementation, and complexity analysis.

---

### 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.

### Example

```plaintext
Input: nums = [1,2,3,1]
Output: true
Explanation: The number 1 appears twice in the array.
```

```plaintext
Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.
```

```plaintext
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: The number 1 appears multiple times, as do the numbers 3, 4, and 2.
```

### Approach

#### 1. Using a Set

Using a set to check for duplicates is a straightforward and efficient approach. Sets do not allow duplicate elements, so we can utilize this property to solve the problem.

##### Algorithm

1. Initialize an empty set.
2. Iterate through each element in the array.
3. For each element, check if it is already in the set.
4. If it is, return `true`.
5. If not, add the element to the set.
6. If the loop completes without finding a duplicate, return `false`.

##### Code

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

##### Complexity Analysis

- **Time Complexity:** \(O(n)\) - where \(n\) is the number of elements in the array. Each lookup and insertion in a set has an average time complexity of \(O(1)\).
- **Space Complexity:** \(O(n)\) - in the worst case, if there are no duplicates, the set will contain all \(n\) elements.

#### 2. Sorting the Array

Sorting the array first can help in identifying duplicates. After sorting, any duplicate elements will be adjacent to each other.

##### Algorithm

1. Sort the array.
2. Iterate through the array.
3. Check if the current element is the same as the next element.
4. If it is, return `true`.
5. If the loop completes without finding duplicates, return `false`.

##### Code

```python
def containsDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False
```

##### Complexity Analysis

- **Time Complexity:** \(O(n \log n)\) - due to the sorting step.
- **Space Complexity:** \(O(1)\) - if sorting in place, or \(O(n)\) - depending on the sorting algorithm used.

#### 3. Using a Dictionary

Using a dictionary (or hashmap) to count occurrences of elements is another effective method.

##### Algorithm

1. Initialize an empty dictionary.
2. Iterate through each element in the array.
3. For each element, check if it is already a key in the dictionary.
4. If it is, return `true`.
5. If not, add the element to the dictionary with a value of 1.
6. If the loop completes without finding a duplicate, return `false`.

##### Code

```python
def containsDuplicate(nums):
    count = {}
    for num in nums:
        if num in count:
            return True
        count[num] = 1
    return False
```

##### Complexity Analysis

- **Time Complexity:** \(O(n)\) - each lookup and insertion in a dictionary has an average time complexity of \(O(1)\).
- **Space Complexity:** \(O(n)\) - in the worst case, if there are no duplicates, the dictionary will contain all \(n\) elements.

### Conclusion

In conclusion, we explored three different approaches to solve the problem of detecting duplicates in an array:

1. Using a set
2. Sorting the array
3. Using a dictionary

The set and dictionary approaches both offer \(O(n)\) time complexity and are straightforward to implement. Sorting the array, while providing an \(O(n \log n)\) solution, can be less optimal but still effective. Depending on the specific constraints and requirements of your application, any of these methods can be a suitable choice.