Looking for a duplicate element in an array?

Question

I saw the interview question as follows:

One number in the array duplicates. note that

A simple solution is as follows:

for(int i=0;i<n;i++){ { dup = false; for(j=0;j<n;j++){ if(i!=j && a[i]= a[j]){ dup = true; } if(dup == true) return a[i] } } 

But I want to implement it in O (n log (n)) and in O (n) time. How can i do this?

Answer 1

Array sorting (this can be done in the first O (n Log n)), then the comparison should be performed only for adjacent elements. Or just put the array in a hash table and stop if you find the first key with an exsting entry.

Answer 2

I am responding to "Finding a duplicate element in an array?"

You look for me and j from 0 to <n, and later you check j! = I. Instead, you could form your loops like this:

 for (int i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { if (a[i] == a[j]) { return i; } } } return -1; 

Re-setting dup = false is nonsense. Either dup, or false, or it's true, then you left the code with "return".

Answer 3

Writing previous answers in real code (Java):

O (n log n) time:

  Arrays.sort(arr); for (int i = 1; i < arr.length; i++) if (arr[i] == arr[i - 1]) return arr[i]; throw new Exception(); // error: no duplicate 

O (n) time:

  Set<Integer> set = new HashSet<Integer>(); for (int i = 0; i < arr.length; i++) { if (set.contains(arr[i])) return arr[i]; set.add(arr[i]); } throw new Exception(); // error: no duplicate 

Answer 4

The java.util.TreeSet link in which the Red-Black tree is implemented is O (n * log (n)) .

Answer 5

I recommend using a hash map (in the absence of collisions) to solve it.

  private boolean hasDuplicate(int[] arr) { Map<Integer, Boolean> map = new HashMap(); // find the duplicate element from an array using map for (int i = 0; i < arr.length; i++) { if(map.containsKey(arr[i])) { return true; } else { map.put(arr[i], true); } } return false; } 

Difficulty of time: O (n)

Space Complexity: O (n)

Another approach is sorting and comparing, but sorting adds extra overhead.

Answer 6

Using collections, we can go below the code snippet -

 Set<String> set = new HashSet<String>(); for (String arrayElement : arr) { if (!set.add(arrayElement)) { System.out.println("Duplicate Element is : " + arrayElement); } } 

Answer 7

Find a solution to O (n) complexity as shown below -

 int ar[]={0,1,2,3,0,2,3,1,0,2}; Set <Integer>mySet=new HashSet<>(); for(int n:ar){ if(!mySet.add(n)){ System.out.println(" "+n); } } 

And another process with less spatial complexity O (N) and possibly O (n Log n) -

  public void duplicateElementSolution(int ar[]){ Arrays.sort(ar); for(int i=0;i<(ar.length-1);i++){ if(ar[i]==ar[i+1]){ System.out.println(" "+ar[i]); } } } 

Answer 8

(The question in its current form is a bit confusing - my answer suggests that the question is to find two numbers in the array that sum with the given value)

Since this array is unsorted, I assume that we are not allowed to sort the array (i.e. this array order cannot be changed).

The simplest IMHO solution is to iterate over each x number and verify that Ix occurs anywhere in arrays. This is essentially what your O (n ^ 2) solution makes.

This can be reduced to O (n) or O (nlogn), speeding up the search using some quick data structure. Basically, when we iterate over an array, we ask if there is an Ix in the set.

Code (in Python):

 l=[1,2,3,4,5,6,7,8,9] seen=set() I=11 for item in l: if I-item in seen: print "(%d,%d)"%(item,I-item) seen.add(item) 

The complexity of the solution depends on the complexity of inserting / searching the set data structure that you are using. The hash table-based implementation has O (1) complexity, so it gives you the O (n) algorithm, and the set tree leads to the O (nlogn) algorithm.

Edit:

The equivalent data structure for Python set will be stl::set in C ++ and TreeSet / HashSet in Java. The string Ix in seen converted to seen.contains(Ix) in Java and seen.find(Ix)==seen.end() in C ++.