Solution: Contains Duplicate
Go Back

## 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 1:

``````Input: nums= [1, 2, 3, 4]
Output: false
Explanation: There are no duplicates in the given array.
``````

Example 2:

``````Input: nums= [1, 2, 3, 1]
Output: true
Explanation: '1' is repeating.
``````

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

## Solution

Approach 1: Brute Force

We can use a brute force approach and compare each element with all other elements in the array. If any two elements are the same, we'll return `true`. If we've gone through the entire array and haven't found any duplicates, we'll return `false`.

### Code

Here is the code for this algorithm:

Python3
Python3

Time Complexity The algorithm takes O(N^2) where N is the number of elements in the input array. This is because we need to compare each element with all other elements, which takes O(N^2) time.

Space Complexity The algorithm takes O(1), because we only need a few variables to store the indices, which takes constant space.

### Approach 2: Using Hash Set

We can use the `set` data structure to check for duplicates in an array.

Since a `set` can only hold unique elements, we can check if the elements in the given array are present more than once by adding them to a `set`. This way, we can determine if there are any duplicates in the array.

This approach works as follows:

1. A set named `unique_set` is created to store unique elements.

2. The algorithm then iterates through the input array `nums`.

3. For each element "x" in the array, the algorithm checks if "x" is already in the `unique_set`.

• If "x" is in the `unique_set`, then the algorithm returns True, indicating that a duplicate has been found.

• If "x" is not in the `unique_set`, then the algorithm adds "x" to the `unique_set`.

4. The iteration continues until all elements in the array have been processed.

5. If no duplicates are found, the algorithm returns False.

This approach utilizes the property of sets to store only unique elements, making it an efficient solution for finding duplicates in an array.

### Code

Here is the code for this algorithm:

Python3
Python3

#### Time Complexity

The time complexity of the function can be analyzed as follows:

1. Initialization of the Set: The initialization of the `Set` itself is O(1), but this doesn't impact the overall complexity of the function.

2. For Loop: The loop iterates through each element of the array `nums`.

3. Set Operations:

• `set.contains(x)` or `x in unique_set`: The average time complexity for checking if an element is in a `Set` is O(1), assuming good hash distribution.
• `set.add(x)`: Similarly, adding an element to a `Set` also has an average time complexity of O(1).
• Similarly, `set.count(x)` also has an average time complexity of O(1).

Since all `Set` operations are O(1) on average and are executed once per element of the array, the dominant factor is the number of elements `n` in the array. The loop runs `n` times, and in each iteration, an O(1) operation is performed.

Thus, the overall time complexity of the function is O(n), where n is the number of elements in the input array `nums`. This complexity assumes that the hash functions used are efficient and the elements are well-distributed in the hash table, avoiding worst-case scenarios of hash collisions. In the worst case, the time complexity would be O(n^2) because the `Set` operations can take O(n) time in the worst case.

#### Space Complexity

The algorithm takes O(N), as it stores the numbers in a set.

### Approach 3: Sorting

Another approach is to sort the array first and then check for duplicates.

We'll sort the array and then iterate through it, comparing each element with the next one.

If any two elements are the same, we'll return `true`. If we've gone through the entire array and haven't found any duplicates, we'll return `false`.

### Code

Here is the code for this algorithm:

Python3
Python3

Time Complexity: O(N*logN), where N is the number of elements in the array `nums`. This is because sorting the array takes O(N*logN) time.

Space Complexity: O(1) or O(n), depending on the sorting algorithm used. If an in-place sorting algorithm is used, the space complexity will be O(1). If a sorting algorithm that creates a new array is used, the space complexity will be O(N), where N is the number of elements in the array `nums`.