# Contains Duplicate
**Difficulty:** EASY
[External](https://leetcode.com/problems/contains-duplicate)
Canonical: https://scaleengineer.com/dsa/problems/contains-duplicate
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Bloom Filter](https://scaleengineer.com/algorithms/bloom-filter)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Airbnb](https://scaleengineer.com/companies/airbnb), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Nagarro](https://scaleengineer.com/companies/nagarro), [Siemens](https://scaleengineer.com/companies/siemens), [Visa](https://scaleengineer.com/companies/visa), [Yandex](https://scaleengineer.com/companies/yandex), [ZScaler](https://scaleengineer.com/companies/zscaler), [tcs](https://scaleengineer.com/companies/tcs), [Netflix](https://scaleengineer.com/companies/netflix), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Paycom](https://scaleengineer.com/companies/paycom)
---
## Problem
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,1\]

**Output:** true

**Explanation:**

The element 1 occurs at the indices 0 and 3.

**Example 2:**

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

**Output:** false

**Explanation:**

All elements are distinct.

**Example 3:**

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

**Output:** true

**Constraints:**

* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force Approach
Compare each element with every other element in the array using nested loops to find duplicates.
**Time:** O(n²) where n is the length of the array as we use nested loops · **Space:** O(1) as we only use a constant amount of extra space
**Pros:** Simple to implement; No extra space required; Works well for very small arrays
**Cons:** Very inefficient for large arrays; Time complexity is quadratic; Not suitable for large scale applications
### Explanation
This approach involves using two nested loops to compare each element with every other element in the array. For each element at index i, we compare it with all elements at indices j > i. If we find any match, we return true indicating a duplicate was found. If no duplicates are found after checking all pairs, we return false.

```java
public boolean containsDuplicate(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}
```
### Algorithm
1. Iterate through the array with index i from 0 to n-1
2. For each i, iterate with index j from i+1 to n-1
3. If nums[i] equals nums[j], return true
4. If no duplicates found, return false

## Sorting Approach
Sort the array first and then check adjacent elements for duplicates.
**Time:** O(n log n) where n is the length of the array, dominated by the sorting operation · **Space:** O(1) if using in-place sorting algorithm
**Pros:** Better time complexity than brute force; Simple to implement; No extra space required (if using in-place sorting)
**Cons:** Modifies the original array; Not as efficient as hash set approach; Sorting overhead might be unnecessary
### Explanation
In this approach, we first sort the array in ascending order. After sorting, any duplicate elements will be adjacent to each other. We then iterate through the sorted array once and check if any adjacent elements are equal. If we find equal adjacent elements, we return true indicating a duplicate was found.

```java
public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i-1]) {
            return true;
        }
    }
    return false;
}
```
### Algorithm
1. Sort the input array in ascending order
2. Iterate through the array from index 1 to n-1
3. Compare each element with its previous element
4. If any adjacent elements are equal, return true
5. If no duplicates found, return false

## Hash Set Approach
Use a HashSet to keep track of seen elements while iterating through the array.
**Time:** O(n) where n is the length of the array as we only need to traverse the array once · **Space:** O(n) where n is the length of the array to store elements in the HashSet
**Pros:** Optimal time complexity; Single pass through the array; Original array remains unchanged; Simple to implement
**Cons:** Requires extra space to store the HashSet; Space complexity is linear with input size; HashSet operations have some overhead
### Explanation
This approach uses a HashSet to store elements as we iterate through the array. For each element, we first check if it's already in the set. If it is, we've found a duplicate and return true. If not, we add it to the set. If we complete the iteration without finding any duplicates, we return false.

```java
public boolean containsDuplicate(int[] nums) {
    HashSet<Integer> seen = new HashSet<>();
    for (int num : nums) {
        if (seen.contains(num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}
```
### Algorithm
1. Create an empty HashSet
2. Iterate through each element in the array
3. If current element exists in set, return true
4. Otherwise, add current element to set
5. If no duplicates found, return false

# Solutions
### CSharp

```csharp
public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        return nums.Distinct().Count() < nums.Length;
    }
}
```

### Java

```java
class Solution {
public
  boolean containsDuplicate(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int num : nums) {
      if (!s.add(num)) {
        return true;
      }
    }
    return false;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {boolean} */ var containsDuplicate =
  function (nums) {
    return new Set(nums).size !== nums.length;
  };

```

### CPP

```cpp
class Solution {
public:
  bool containsDuplicate(vector<int> &nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    return s.size() < nums.size();
  }
};

```

### Python

```python
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool: return len(set(nums)) < len(
        nums)  # class Solution ( object ): def containsDuplicate ( self , nums ): """ :type nums: List[int] :rtype: bool """ nums . sort () for i in range ( 0 , len ( nums ) - 1 ): if nums [ i ] == nums [ i + 1 ]: return True return False

```