Saturday, February 25, 2012

How to check or detect duplicate elements in Array in Java

Detecting duplicate elements in Java array is another programming interview question I like. There could be lot of way you can check if your array contains duplicate elements or not and sometime you discover a unique way of checking duplicates by asking this question on Java interview. Beauty of this question is that it has endless number of follow-up question so if interviewee get 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 skill around array of a Java programmer.

Checking Array for duplicate elements Java

In this Java tutorial we will see couple of ways to find if array contains duplicates or not in Java. We will use unique property of Java collection class Set which doesn’t allow duplicates to check java array for duplicate elements.  Here are five ways we can check if an array has duplicates or not:

1) brute force method which compares each element of Array to all other elements and return true if it founds duplicates. Though this is not an efficient choice it is the one which first comes in mind.

2) 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  corresponding Set will be smaller than original Array if Array contains duplicates otherwise size of both Array and Set will be same.

3) One more way to detect duplication in java array is adding every element of array into HashSet which is a Set implementation. Since add(Object obj) method of Set returns false if Set already contains element to be added, it can be used to find out if array contains duplicates in Java or not.

How to find or detect duplicate elements in Array in JavaIn next section we will complete code example of all three ways of duplicate detection on Array in java. Remember this discussion is just confirming whether array contains duplicate or not , its not finding out actual duplicate elements from Array, though you can easily extend example Java program to accomplish that task based on your requirement.

Code Example of checking duplicate on Array in Java

Here is complete code sample of all 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 elements 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 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 example, there can be other pure programming solution as well. You may be asked to detect duplicates without using Java API in real interview. Let us know if you come across some other good way of checking duplicates in array without using Java API.

Other Java Tutorials you may find useful

16 comments :

Stanley F. said...

Hi,

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

michee said...

if(inputSet.size()
return true;
}


I think that If condition is incomplete.

Anonymous said...

followup questions most likely will be:

How 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)

Javin @ google interview question said...

@michee, you pointed right if condition was incomplete it should be inputSet.size()<inputList.size(). Corrected. Thanks for pointing it out.

michee said...

Also in function bruteforce:

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

Javin @ Sort array in java said...

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.

michee said...

you're right i didn't see that 'i!=j' part :)
I don't do code review, i'm just a php dev learning java and i like it:)

michee said...

ps: my way it's more optimal!:P

Anonymous said...

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

Anonymous said...

Without using API you may sort the array with some fast algorithm and do linear search for adjacent the same values.

Anonymous said...

string is like this:"Hello abcdef ABCDEF 1234 12AB"

and I need o/p like this:Hello a-f A-F 1-4 1-B
please tell me if any one know.

RC said...

In the brute force method, why are you going over the whole array again in the inner loop?

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

Javin @ Print array in Java said...

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.

Nat JM said...

public static boolean bruteforce(String[] input) {
for (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.

sana kakou said...

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 ;)

Krishna said...

Java program to print integers which occurs thrice in the array:

package 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]);
}
}

}

Post a Comment