CODEWITHSUNDEEP
javaalgorithmcollections
Sam2016
Sam2016

Reputation: 998

Reduce the time complexity of the code to find duplicates in an Array from N*N

I was recently asked in an interview to write code to determine if an array of integers contains duplicates simple as it was i confidently told him that i would iterate the elements and add each one to an new array if the array doesn't contain the element already if it does i return true else return false complexity

the code would be like this 

//complexity is N*N
    public static boolean findIfArrayHasDuplicates(int[] array){


        int[] newArr = new int[array.length];
        List<Integer> intList = new ArrayList<Integer>();

        for (int var: array){
            if(intList.contains(var)){
                return true;
            }else{
                intList.add(var);
            }
        }
        return false;
    }   
}

He asked me to calculate the time complexity of the code i have written

I answered

N for iteration of the loop N(N+1)/2 for finding if the element exists in in new list N for adding the elements in the list

total N +N + N*N/2 + N/2 in O() notation multiplying by 2 and simplifying as N tends to infinity this can be simplified O(N^2)

he went on to ask me if there is any better way i answered add the elements to a set and compare the size if the size of set is less than than of the array it contains duplicates , asked what is the complexity of it guess what its still O(N^2) because of the code that adds elements to the set will have to first see if its in the set already . How can I reduce the complexity from O(N^2) using as much as memory needed. Any ideas how this can be done ?

Upvotes: 0

Views: 2931

Answers (3)

I. Ahmed
I. Ahmed

Reputation: 2534

The complexity of code provided is O(N^2). However, the code given follows is complexity O(N). It uses HashSet, which required O(1) operation to insert and search.

    public static boolean findIfArrayHasDuplicates(int[] array){

            HashSet<Integer> set = new HashSet<Integer>();
            set.add(array[0]);

            for (int index = 1; index < array.length; index++) {
                    if(!set.add(array[index]))
                            return true;
            }

            return false;
     }

Upvotes: 1

justgivememyicecream
justgivememyicecream

Reputation: 270

I think it would be useful if you would look at basic working mechanisms of a HashSet. A HashSet is internally an array, but data accesses, such as "checking if an element exists", or "adding/deleting an element", is of time complexity O(1), because it takes on a mapping mechanism to map an object to the index storing it. For example, if you have a HashSet and an integer and you do a hashSet.contains(integer), the program will first take the integer and calculate the hash code of it, and then use the mapping mechanism (differs from implementation to implementation) to find the index storing it. Say we have a hash code of 4, and we map to an index of 4 using the simplest mapping mechanism, then we will check if the 4th element of the underlying array is empty. If it is, hashSet.contains(integer) will return true, otherwise false.

Upvotes: 2

Eran
Eran

Reputation: 393791

he went on to ask me if there is any better way i answered add the elements to a set and compare the size if the size of set is less than than of the array it contains duplicates , asked what is the complexity of it guess what its still NN because of the code that adds elements to the set will have to first see if its in the set already

That's wrong. If you are adding the elements to a HashSet, it takes expected O(1) time to add each element (which includes checking if the element is already present), since all you have to do is compute the hashCode to locate the bin that may contain the element (takes constant time), and then search the elements stored in that bin (which also takes expected constant time, assuming the average number of elements in each bin is bound by a constant).

Therefore the total running time is O(N), and there's nothing to improve (you can't find duplicates in less than O(N)).

Upvotes: 7

Related Questions