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;
        ch.add(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

• Remove Duplicates from sorted array
• Median of two sorted arrays
• Intersection of two arrays
• Add One to number
• Rotate Array

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