Question

Given a generic array with ‘n’ items (not only integers). Give a solution for checking whether there are any duplicate elements in the array or not? You just need to return a boolean (true or false). State the complexity of your solution. Can you come up with another solution that has O(n logn) complexity? Explain.

Answer 1

/*

Please read comments and see the program and output

Approach1: Use Set in java, which always keep unique element,

            We can easily check, duplicate is there or not using .contains(element) method

            It works in O(1) time comlexity due to internal HashMap implementation.

            So this is best approach.

Approach2: Use ArrayList in java, which runs its complexity with O(n) for contains(element)

           So any element which is there or not, totally it would take O(n*n) time

Approach3: Sort element and use any collections, like ArrayList, using single iteration,

            make comparision like

                currelement == prevElement

            then duplicate is there

            otherwise "There is no duplicate element"

            Since best sorting approach time complexity is O(nlogn)

            and single iteration time complexity is O(n),

            Hence total time complexity would be O(nlogn) + O(n) equals to O(nlogn)

*/

import java.util.*;

class Duplicate {

    //Approach 1, using Set

    static boolean isDuplicateUsingSet(int [] array) {

        Set<Integer> set = new HashSet<Integer>();

        for(int i: array)

            if(set.contains(i))

                return true;

            else

                set.add(i);

        return false;

    }

    //Approach 2, Using ArrayList

    static boolean isDuplicateUsingArrayList(ArrayList<Integer> array) {

        //Check for "one"

        for(int i: array) {

            if(array.contains(2))

                return true;

        }

        return false;

    }

    public static void main(String arg[]) {

        ArrayList<Integer> list  = new ArrayList<Integer>();

        list.add(11);

        list.add(2);

        list.add(3);

        list.add(11);

        Set<String> stringArray = new HashSet<String>();

        stringArray.add("one"); //Gives true means unique element,

        stringArray.add("two"); ////Gives true means unique element,

        stringArray.add("three"); // Gives false means element is duplicate

        int a[] = {1,33,2,1};

        System.out.println("int array is " );

        for(int i:a)

            System.out.print(i+" ");

        System.out.println();

        System.out.println("Duplicate is in array " + isDuplicateUsingSet(a));

        System.out.println("Arraylist element is " );

        for(int i:list)

            System.out.print(i + " ");

        System.out.println();

        System.out.println("Duplicate is in arrayList " + isDuplicateUsingArrayList(list));

    }

}

/* Output*/

/* Similary for any generic object , this thing can be done in same manner*/

/* Thanks*/