# Leetcode 217: Contains Duplicate

## Table of Contents

This question marks the first problem when working on duplicate data, either integers or strings etc.

Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies.

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

**Test case #1**

```
Input: nums = [1,2,3,1]
Output: true
```

**Test case #2**

```
Input: nums = [1,2,3,4]
Output: false
```

## Thought Process

My first thoughts when looking at this problem and the questions I have are:

- So, if two integers are repeating, which one should I return?
- What are the constraints? Do you have any time & space constraints for this problem?

Once the above questions are discussed with the interviewer, I will propose different ways to solve this problem. The ones that come to my mind right now are

- Naive approach
- Sorting the array
- Memoization / Hash table approach

## Approach 1: Naive / Linear search

### Intuition

In this approach, we iterate through the `nums`

array twice to find the pair of elements that are duplicates.

### Algorithm

- Iterate through each element of the array using a loop with index
`i`

from`0`

to`length - 1`

.For each`i`

, go to the next step.- Within the outer loop, iterate through the remaining elements of the array using a loop with index
`j`

from`i + 1`

to`length - 1`

. - For each
`j`

, If`nums[i]`

is equal to`nums[j]`

, return`true`

indicating that duplicates are found.

- Within the outer loop, iterate through the remaining elements of the array using a loop with index
- If the entire array has been checked and no duplicates are found, return
`false`

.

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

### Complexity Analysis

**Time complexity**: Time is `O(N^2)`

, where `N`

is the number of elements in the prices array. We are traversing the entire array twice.

For an array of

integers, there are *n*`n(n−1)/2`

pairs of integers. Hence, the time is quadratic.

**Space complexity**: Space is `O(1)`

, no extra space is allocated.

## Approach 2: Sorting

### Intuition

Isn't sorting an easy approach? We sort the `nums`

array, and the duplicate elements are next to each other. A linear iteration through the array is enough to find the duplicate value.

### Algorithm

- Sort the integer array using
`Arrays.sort`

method. Sorts the array into ascending numerical order - Use a for-loop from
`0`

to`nums.length - 2`

. We run into`ArrayIndexOutOfBoundsException`

if we run the loop until`nums.length - 1`

. - Check if the current and next index are the same,
`nums[i] == numd[i + 1]`

.

```
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
}
```

### Complexity Analysis

**Time complexity**: Time is `O(NLogN)`

, where `N`

is the number of elements in the prices array. `nlogn`

is for sorting the array, in here the once Java uses is Dual-Pivot Quicksort.

**Space complexity**: Space is `O(1)`

, no extra space is allocated. We sorted the input array.

## ✅ Approach 3: Memoization [Accepted]

### Intuition

We store each element in the hash table, and when we find an already existing value in hashtable, we return `true`

as per problem statement.

### Algorithm

- Create a hash table named
`hs`

to store unique elements. - Use a loop to iterate through each element of the input array
`nums`

.- For each element, check if it is already present in the HashSet (
`hs`

) using`hs.contains(nums[i])`

. - If the element is found in the HashSet, return
`true`

immediately.

- For each element, check if it is already present in the HashSet (
- If the element is not found in the HashSet, add it to the HashSet using
`hs.add(nums[i])`

. - If the loop completes without finding any duplicates, return
`false`

, indicating that there are no duplicate elements in the array.

```
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> hs = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (hs.contains(nums[i])) {
return true;
}
hs.add(nums[i]);
}
return false;
}
}
```

### Complexity Analysis

**Time complexity**: Time is `O(N)`

, where `N`

is the number of elements in the prices array.

**Space complexity**: Space is `O(N)`

, for storing the `N`

elements in the hashtable.

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.