# Leetcode #217. Contains Duplicate — Solution

Today we are going to solve Leetcode 217. Contains Duplicate.

**Problem Statement**

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

**Example 1:**

**Input:** [1,2,3,1]

**Output:** true

**Example 2:**

**Input: **[1,2,3,4]

**Output:** false

**Example 3:**

**Input: **[1,1,1,3,3,4,3,2,4,2]

**Output:** true

**Solution**

This problem can be approached in many ways.

**Naive Solution**

In the naive approach, we will check whether a number is repeated or not. For that, we will choose one number and will search for it in the array. If that element occurs in the array in other places we return `true`

. In the end, if we have not found any repetitions, we can return `false`

. This will give us a **Time Complexity of **`O(n^2)`

** **where `n`

is the length of the array.

**Sorting**

We can also use sorting to solve this problem. At first, we will sort the array, and then check if any adjacent elements are equal, if it is equal we can return `true`

. This approach is better than the previous one, for sorting we require `O(nlogn)`

time and for searching adjacent elements, we require `O(n)`

time. Therefore the overall **Time Complexity will be **`O(nlogn)`

** .**

**Hashing**

Whenever there is a problem associated with occurrence, duplication and frequency we may be able to apply hashing to solve that problem. In this case, we are going to use `HashSet`

to solve the problem. We will store each element of the array in an `HashSet`

and if there is an occurrence, we can return `true`

. If we do not find any repetitions, we can return false.

**The time complexity for this approach is **`O(n)`

** and space complexity is **`O(n)`

, because we are using extra space for the HashSet.

All the codes can be found here.