Detecting duplicate elements in Java array is another programming interview question I like. There could be a lot of ways you can check if your array contains duplicate elements or not and sometimes you discover a unique way of checking duplicates by asking this question on Java interview. The beauty of this question is that it has an endless number of follow-up question so if interviewee gets through this question you can ask to him about time complexity and space or to improve his algorithm to make it fast .you can even ask to find those duplicate elements in Array which even can go from one duplicate to many repeating elements in Array. As I said you can really test programming skills around an array of a Java programmer.
In the next section, we will complete a code example of all three ways of duplicate detection on Array in java. Remember this discussion is just confirming whether an array contains duplicate or not , it's not finding out actual duplicate elements from Array though you can easily extend example Java program to accomplish that task based on your requirement.
This is also one of the popular programming interviews questions, asked in several interviews. I also suggest you solve problems from these coding interview books and courses. One of the best resources to prepare for software developer interviews.
Checking Array for duplicate elements Java
In this Java tutorial, we will see a couple of ways to find if an array contains duplicates or not in Java. We will use the unique property of the Java collection class Set which doesn’t allow duplicates to check the java array for duplicate elements. Here are five ways we can check if an array has duplicates or not:
1. Brute Force Algorithm
The brute force method compares each element of Array to all other elements and returns true if it finds duplicates. Though this is not an efficient choice it is the one that first comes to mind.
2. Using Set Data Structure
Another quick way of checking if a Java array contains duplicates or not is to convert that array into Set. Since Set doesn’t allow duplicates size of the corresponding Set will be smaller than the original Array if Array contains duplicates otherwise the size of both Array and Set will be the same.
3. Using HashSet in Java
One more way to detect duplication in the java array is adding every element of the array into HashSet which is a Set implementation. Since the add(Object obj) method of Set returns false if Set already contains an element to be added, it can be used to find out if the array contains duplicates in Java or not.
Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join these free Data Structure and Algorithms courses to fill the gaps in your understanding.
Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join these free Data Structure and Algorithms courses to fill the gaps in your understanding.
In the next section, we will complete a code example of all three ways of duplicate detection on Array in java. Remember this discussion is just confirming whether an array contains duplicate or not , it's not finding out actual duplicate elements from Array though you can easily extend example Java program to accomplish that task based on your requirement.This is also one of the popular programming interviews questions, asked in several interviews. I also suggest you solve problems from these coding interview books and courses. One of the best resources to prepare for software developer interviews.
Code Example of checking duplicate on Array in Java
Here is a complete code sample of all the above methods to check if your array contains duplicates or not.
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CheckDuplicatesInJavaArray {
public static void main(String args[]) {
String[] withDuplicates = new String[] {"one","two","three","one"};
String[] withoutDuplicates = new String[] {"one","two","three"};
System.out.println("Checking array with duplicate using brute force: " + bruteforce(withDuplicates));
System.out.println("Checking array without any duplicate using brute force: " + bruteforce(withoutDuplicates));
System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingSet(withDuplicates));
System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingSet(withoutDuplicates));
System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingAdd(withDuplicates));
System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingAdd(withoutDuplicates));
}
/*
* brute force way of checking if array contains duplicates in Java
* comparing each element to all other elements of array
* complexity on order of O(n^2) not advised in production
*/
public static boolean bruteforce(String[] input) {
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input.length; j++) {
if (input[i].equals(input[j]) && i != j) {
return true;
}
}
}
return false;
}
/*
* detect duplicate in array by comparing size of List and Set
* since Set doesn't contain duplicate, size must be less for an array which contains duplicates
*/
public static boolean checkDuplicateUsingSet(String[] input){
List inputList = Arrays.asList(input);
Set inputSet = new HashSet(inputList);
if(inputSet.size()< inputList.size())
return true;
}
return false;
}
/*
* Since Set doesn't allow duplicates add() return false
* if we try to add duplicates into Set and this property
* can be used to check if the array contains duplicates in Java
*/
public static boolean checkDuplicateUsingAdd(String[] input) {
Set tempSet = new HashSet();
for (String str : input) {
if (!tempSet.add(str)) {
return true;
}
}
return false;
}
}
Output:
Checking array with duplicate using brute force: true
Checking array without any duplicate using brute force: false
Checking array with duplicate using Set and List: true
Checking array without any duplicate using Set and List: false
Checking array with duplicate using Set and List: true
Checking array without any duplicate using Set and List: false
That’s all on how to check if an Array contains duplicate or not in Java. You see we have used Java Collection API in two of our examples, there can be other pure programming solutions as well. You may be asked to detect duplicates without using Java API in the real interview. Let us know if you come across some other good way of checking duplicates in an array without using Java API.
Other Java Tutorials you may find useful
Hi,
ReplyDeleteI don't know, whether it's a performant way, but the first method I thought of, was: Sort the array and then check if there are two equal items that directly follow each other.
if(inputSet.size()
ReplyDeletereturn true;
}
I think that If condition is incomplete.
followup questions most likely will be:
ReplyDeleteHow to find duplicate items in Array? (Actual item not just confirmation that array contains duplicate)
How to remove duplicates in Java Array?
How to find count of duplicates in Java array ?(e.g. how many times a particular element is appearing in array)
@michee, you pointed right if condition was incomplete it should be inputSet.size()<inputList.size(). Corrected. Thanks for pointing it out.
ReplyDeleteAlso in function bruteforce:
ReplyDeletepublic static boolean bruteforce(String[] input) {
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input.length; j++) {
I think j should start from i+1 . Because every element will be equal to itself.
michee dude you are picking it very well, must be good in code review :) you are correct it should can start with i+1 but if you see I have put an extra condition i != j to not consider same element.
ReplyDeleteyou're right i didn't see that 'i!=j' part :)
ReplyDeleteI don't do code review, i'm just a php dev learning java and i like it:)
ps: my way it's more optimal!:P
ReplyDeleteif you don't want duplicate in array than convert array into set. this way you don't need to check array for duplicates, because array backed up by Set doesn't contains repeated element. I guess this is best way to remove duplicates from array.
ReplyDeleteWithout using API you may sort the array with some fast algorithm and do linear search for adjacent the same values.
ReplyDeletestring is like this:"Hello abcdef ABCDEF 1234 12AB"
ReplyDeleteand I need o/p like this:Hello a-f A-F 1-4 1-B
please tell me if any one know.
In the brute force method, why are you going over the whole array again in the inner loop?
ReplyDeletej should start at i + 1, not at zero. Because all the elements before i + 1 have already been compared to the rest of the array.
RC, you are correct, it can be like that, as Michee already pointed out,but if you see I have put an extra condition i != j to not consider same element.
ReplyDeletepublic static boolean bruteforce(String[] input) {
ReplyDeletefor (int i = 0; i < input.length; i++) {
for (int j = 0; j < input.length; j++) {
As RC said, j should start at i + 1 because if items at index 5 and 3 are the same, it will be found when i = 3 (and j = 5) so no need to look for it when i = 5 --> you only need to look forward, thus making the brute force method run faster than what you have written.
It isn't about avoiding the case i = j (which you have catered for with i != j), it is about reducing the loop j, thus speeding up the algorithm.
but if it is " one" or " one " or "one " it will not be fund that's why i think we have to use trim if we suppose that " one" is equal to "one" ;thxxxx for the tuto ;)
ReplyDeleteJava program to print integers which occurs thrice in the array:
ReplyDeletepackage com.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ArrayTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {1,2,3,4,1,2,4,3,2,3,4,4,4,1,5,6,5,7,5,6,8,7,6,7};
int[] finalArray = new int[20];
System.out.println(array);
Arrays.sort(array);
System.out.println(array);
int value=0;
int counter=1;
for (int i = 0; i < array.length-1; i++)
{
if (array[i] == array[i+1]) {
counter++;
} else {
counter=1;
}
if(counter==3) {
finalArray[value++] =array[i];
} else if (counter==4) {
finalArray[--value]=0;
}
}
for (int i = 0; i < finalArray.length-1; i++)
{
System.out.println(finalArray[i]);
}
}
}
Hey Guys ,how about this:
ReplyDeletepublic static boolean checkDuplicateUsingAdd(String[] input) {
Map elementMap = new HashMap();
for (String str : input) {
Boolean wasInserted = elementMap.get(str);
if (wasInserted!=null) {
return false;
}
elementMap.put(str,Boolean.TRUE);
}
return true;
}
How about perfomance of this solution O(n)?
Thanks for ur Answer.Its very helpful.
ReplyDeleteI feel this can help
ReplyDeletepublic class ArrayDuplicates {
public static void main(String[] args) {
int[] arrayValues = new int[4];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < arrayValues.length; i++) {
arrayValues[i] = sc.nextInt();
}
Set setValue = new HashSet();
for (int i : arrayValues) {
setValue.add(i);
}
if (setValue.size() < arrayValues.length) {
System.out.println("There are duplicates");
} else {
System.out.println("There are no duplicates");
}
}
}
Hello, I found way to get duplicate number in array without using java API.
ReplyDeletepublic class DuplicateFinder {
public void isDuplicate(int[] inputArray) {
int actualSum = 0, desiredSum = 0, difference = 0, duplicateNumber = 0;
for (int i = 0; i < inputArray.length; i++) {
actualSum = actualSum + inputArray[i];
}
desiredSum = (inputArray.length) * (inputArray.length + 1) / 2;
difference = desiredSum - actualSum;
if (difference != 0) {
duplicateNumber = inputArray.length - difference;
System.out.println(duplicateNumber + " "
+ "is duplicate number in array.");
} else {
System.out.println("No duplicate in array.");
}
}
public static void main(String[] args) {
DuplicateFinder duplicateFinder = new DuplicateFinder();
int[] duplicateArray = { 1, 2, 3, 3 };
int[] noDuplicateaArray = { 1, 2, 3 };
duplicateFinder.isDuplicate(duplicateArray);
duplicateFinder.isDuplicate(noDuplicateaArray);
}
}
Im having a conflict with using text file as input, containing the same array elements. The problem is that the output shows that both duplicate elements are considered false(ex. false output for one=one)
ReplyDelete@Samruddhi Jadhav
ReplyDeleteint[] duplicateArray = { 1, 2, 3, 3,5,5 }; is returning 4 for duplicateArray.
@Javin Paul
ReplyDeleteIn an interview i were asked to
1)write a program to find how many times each duplicate occurred?
can you please give me an idea to do this in a post or comment.
Thank you.
U may use Arrays.asList(T...arr) to fetch list backed by that array and iterate/loop over that list to pass each element with list to Collections.frequency(list, obj) to get the frequency for that element. Store that with element as key, preferably to LinkedHashMap for order. U'll hv that map now keeping record of no of times each duplicate occurs
Delete@Anonymous, you can also use a hash table to solve your problem, i.e. to find frequency of each word, any word with more than one count is duplicate, you can see code example here
ReplyDeletehi guys the problem given is to find duplicates in a given array
ReplyDelete// no need to know the complex stuff like hashset or brute stuff algorithm my code as follows
public class DuplicateElementsInArray{
public static void main(string args[])
{
int[] mynumbers = new int[] {1,3,5,4,1,2,3,5,4,7,6,7};//step1-i created an unsorted array
Arrays.sort(mynumbers);// step2- smart code what ever the input just sort it using this logic
System.out.println(Arrays.toString(mynumbers) // print the sorted array for ur convinience
for( i=0;i<mynumbers.length;i++)
{
if(mynumbers[i] == mynumbers[i-1])
{
System.out.println("Duplicate number in the given sequence is :" +mynumbers[i])
}
}
}
//thats it no need of complex stuff u will get the solution :p :p
public class FindDuplicate {
ReplyDeletepublic static void main(String[] args) {
Integer[] arr = new Integer[]{6, 2, 4, 4, 1,3,6};
List duplicate =new ArrayList();
Arrays.sort(arr);
for(int a:arr)
System.out.println(a);
for(int i =0;i<arr.length-1;i++)
{
if(arr[i]==arr[i+1])
{
duplicate.add(arr[i]);
}
}
System.out.println("Duplicate Values are =="+duplicate);
}
}