This question should be asked more precisely: How can array of size N filled with numbers up to N (0 to N – 1) be scanned for duplicate values (or more) with one scan (O(n))?

The answer lies in the body of the question: The fact that the array is filled with numbers up to N only, implies that a helper array of size N can be used to store the number of times each number appears in the first array. The value of the number in the first array is used as an index in the helper array. For example, if the first value in the array is: 5, then the 5th element in the helper array is incremented by 1. Of course, before incrementing the value in the helper array, we check if it is larger than 0. If it is larger than 0, the value of the first array was already counted once, and this current value is a duplicate.

The code of such method is very simple, lets have a look:

public class ArrayDuplicates {public static boolean isDuplicate(int[] arr){int size = arr.length;int[] helperArr = new int[size];for (int i = 0; i < size; i++){if (helperArr[arr[i]]++ > 0){return true;}}return false;}public static void main(String[] args){System.out.println(isDuplicate(new int[] { 2, 1, 0 }));System.out.println(isDuplicate(new int[] { 2, 0, 2 }));}}

Note, that incrementing the index of the helper array (according to the value from the first array) and checking if we have already counted this number is all done the “if” sentence.

Good one..

ReplyDeleteIs it Possible to find a string array for duplicates with this complexity (o(n))?.

If you mean: find duplicate characters in a string, the easiest way would be, to iterate the string char by char and put each char in a Set (or chars of course). On each iteration, before inserting the new char to the Set, check if it already exists (using the "contains" method). If the new char already exists in the Set, it is a duplicate char. Note, that a Set is actually a Map, so using the "contains" method should be pretty efficient to give you a good running time of O(n).

ReplyDeleteSystem.out.println(isDuplicate(new int[] { 2, 0, 1,4,6 ,6}));

ReplyDeletegiving ArrayIndexOutOfBoundsException

Of course it does. Because the array contains the number "6". If you will look at the definition of the problem, you will see that the numbers that can be in the array are only from 0 to N - 1. Which means that "6" is not allowed. Of course supporting up to N number and even up to N * 2 (and so on...) can be added very easily.

ReplyDeleteWhy aren't you simply using a Map to store the values?

ReplyDeleteYo can first find out the max number in 'arr' and then create a 'helperArr' of that size to avoid ArrayIndexOutOfBoundsException. More elegant way in O(n) time complexity.

ReplyDeleteThis an "Interview Question". The whole point is that the terms have been set for you.

ReplyDelete