# Contains Duplicate

{% hint style="info" %}
Array, Hash Table
{% endhint %}

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
```

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
```

### Solutions

The key insight to solve this problem is to realize that we need to keep track of the elements we have already encountered as we iterate through the array. If we encounter an element that we have seen before, we can immediately return `true` because we have found a duplicate. If we finish iterating through the array without finding any duplicates, we return `false`.

#### **Approach – Brute Force Technique**

The brute force approach involves checking each pair of elements in the array. If any pair is equal, return `true`. If no pairs are equal, return `false`.

**Steps**

1. **Iterate over the array**: The outer loop (index `i` from 0 to `nums.Length - 1`) iterates over each element in the array.
2. **Check for duplicates**: For each element `nums[i]`, the inner loop (index `j` from `i + 1` to `nums.Length - 1`) checks all the following elements in the array to see if they are equal to `nums[i]`.
3. **Return true if a duplicate is found**: If `nums[i]` is equal to `nums[j]`, it means we have found a duplicate, so we immediately return `true`.
4. **Return false if no duplicates are found**: If we finish iterating through the array without returning `true`, it means we have not found any duplicates, so we return `false`.

```csharp
public class Solution {
    public bool 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;
    }
}

```

> Complexity

* **Time Complexity:** O(n^2)
* **Auxiliary Space:** O(1)

#### **Approach – Sorting Technique**

This approach involves sorting the array first, then checking each pair of adjacent elements. If any pair is equal, return `true`. If no pairs are equal, return `false`.

**Steps**

1. **Sort the array**: The `Array.Sort(nums)` function sorts the array in ascending order. This operation has a time complexity of O(n log n), where n is the number of elements in the array.
2. **Iterate over the array**: The loop `for (int i = 0; i < nums.Length - 1; i++)` iterates over each element in the array, except the last one. This is because we're comparing each element with its next neighbor, and the last element doesn't have a next neighbor.
3. **Check for duplicates**: Inside the loop, the `if (nums[i] == nums[i + 1])` statement checks if the current element is equal to the next element. Because the array is sorted, any duplicate elements will be adjacent to each other. So, if the current element is equal to the next element, it means we have found a duplicate, and we immediately return `true`.
4. **Return false if no duplicates are found**: If we finish iterating through the array without returning `true`, it means we have not found any duplicates, so we return `false`.

```csharp
public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums); //n log n
        for (int i = 0; i < nums.Length - 1; i++) //n times
         {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}
```

> Complexity

* **Time Complexity:** O(n log n)
* **Auxiliary Space:** O(1)

#### **Approach – Hash Table Technique**

We can use a data structure like a HashSet that allows for efficient insertions and lookups. We iterate through the array and insert each element into the HashSet. If an element is already in the HashSet, we return `true`. If we finish iterating through the array without finding any duplicates in the HashSet, we return `false`.

**Steps**

1. **Initialize**: Create a new HashSet `set`. A HashSet is a collection of unique elements.
2. **Iterate over the array**: The `foreach` loop iterates over each element `num` in the array `nums`.
3. **Check for duplicates**: Inside the loop, the `if (set.Contains(num))` statement checks if `num` is already in the HashSet `set`. If it is, it means we have found a duplicate, so we immediately return `true`.
4. **Add element to the set**: If `num` is not in the set, we add it to the set using `set.Add(num)`. This step is done for each element in the array.
5. **Return false if no duplicates are found**: If we finish iterating through the array without returning `true`, it means we have not found any duplicates, so we return `false`.

```csharp
public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> set = new HashSet<int>();
        foreach (int num in nums) {
            if (set.Contains(num)) {
                return true;
            }
            set.Add(num);
        }
        return false;
    }
}
```

> Complexity

* **Time Complexity:** O(n)
* **Auxiliary Space:** O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/contains-duplicate.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.