### Find First Duplicate in an Array Java - The Coding Shala

Home >> Interview Questions >> first duplicate element
In this post, we will discuss how to find first duplicate in an array and will implement its solution in Java.

# First Duplicate in an Array Problem

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example 1:
For a = [2, 1, 3, 5, 3, 2], the output should be firstDuplicate(a) = 3.
There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

# First Duplicate in an Array Java Solution

Approach 1:
We can use HashSet. If a number repeat, we will return that. It will take an additional O(n) space to store in HashSet.

Java Program:
```int firstDuplicate(int[] a) {
HashSet<Integer> ch = new HashSet<>();
for(int i=0;i<a.length;i++){
int num = a[i];
if(ch.contains(num)) return num;
}
return -1;
}
```

Approach 2:
This approach is more efficient. we can modify the same array. In the given problem given numbers are in the range of 1 to a.length so we can modify the current number's sorted index. In this way, if a number repeats the number's sorted index is already modified.

Java Program:
```int firstDuplicate(int[] a) {
for(int i=0;i<a.length;i++){
if(a[Math.abs(a[i])-1]<0) return Math.abs(a[i]);
a[Math.abs(a[i])-1] *= -1;
}
return -1;
}
```

Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.