Question 4: Find Duplicate Element in Array

Find duplicate element in an array

Question 4

You are given an array of size n. One of the elements of the array appears twice in the array. Every other element appears once. You need to find the duplicate element.

For example

Input: {3, 6, 9, 0, 4, 7, 6}

Output: The duplicate is 6

 

Solution 1: Brute Force Approach (Inefficient, O(n2))

In this approach, you iterate through the array and compare each element with every other element in the array until you find a match.

The Java code is given below

 

/*
 * Find duplicate in array using brute force
 * Written by Kindson the Genius
 */
public class FindDuplicateElement1 {
	
	public static void findDuplicateElement(int[] A) {
		
		for(int i = 0; i < A.length-1; i++) {
			
			for(int j = i+1; j < A.length; j++ ) {
				if(A[i] == A[j]) {
					System.out.println("Duplicate at " + i + " and " + j);
					return;
				}
			}			
		}//end of for loop		
		System.out.println("No duplicates found");		
	}//end of function

	
	//Main method to test the function
	public static void main(String[] args) {
		int ar[] = {4, 5, 9,4};
		findDuplicateElement(ar);
	}
}

 

 

Solution 2 – Using Hashing – O(n)

In this solution, we iterate through the array once. For each iteration, we check if the value is in the hash table. If yes, then it’s a duplicate. If not, then we insert it into the hash table.

The Java code is given below:

import java.util.HashMap;
import java.util.Map;

/*
 * Find duplicate in array using hashing
 * Written by Kindson the Genius
 */

public class FindDuplicateElement {
	
	//Return indexes of duplicate
	public static void findDuplicateElements(int A[]) {
		
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		
		for(int i = 0; i < A.length; i++) {
			
			if(map.containsKey(A[i])) {
				System.out.println("Duplicates at " + map.get(A[i]) + " and " + i);
				return;
			}
			
			map.put(A[i], i);
		}
		
		System.out.println("No duplicate found");
	}
	
	
	public static void main(String[] args) {
		int[] ar = {5, 7, 6, 5, 2};
		findDuplicateElements(ar);
	}
}

 

 

Solution 3 – Using Sorting

In this approach, we first sort the array. Sorting takes logarithmic time. Then the duplicate element would then be side by side.

Then we loop through the array comparing each element with the immediate next element. Once there is a match then we return. But the challenge with this approach is that the index of the elements after sorting would change. So we only return the duplicate element and not the index.

The Java code is given below:

 

/*
 * Find duplicate in array using sorting
 * Written by Kindson the Genius
 */
import java.util.Arrays;

public class FindDuplicateElement2 {
	
	public static void findDuplicateElement(int A[]) {
		
		//First sort the array
		Arrays.sort(A);
		if(A.length <= 1) {
			System.out.println("Unable to proceed");
			return;
		}
		
		for(int i = 0; i < A.length-1; i++) {
			if(A[i] == A[i+1]) {
				System.out.println("Duplicate element is " + A[i]);
				
				return;
			}
		}
		
		System.out.println("No duplicated found");
	}

	public static void main(String[] args) {
		int ar[] = {3,4, 5, 6, 6};
		findDuplicateElement(ar);
	}

}