CODEWITHSUNDEEP
javac++algorithm
mindtree
mindtree

Reputation: 227

Finding duplicate element in an array?

I saw a interview question as follows:

One number in array is duplicating.Find it

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 it?

Upvotes: 0

Views: 22590

Answers (9)

卢声远 Shengyuan Lu
卢声远 Shengyuan Lu

Reputation: 32004

Reference java.util.TreeSet which is implemented Red-Black tree underlying, it's O(n*log(n)).

Upvotes: -1

Ayesha Aleem
Ayesha Aleem

Reputation: 21

var containsDuplicate = function(nums) {
    const set = new Set();
    for (const num of nums) {
        if (set.has(num)) {
            return true; // Found a duplicate
        }
        set.add(num);
    }
    return false; // No duplicates found
};

Upvotes: 0

pkm1986
pkm1986

Reputation: 305

Find O(n) complexity solution as 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 lesser space 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]);
        }
    }
  }

Upvotes: 0

Sachchidanand Singh
Sachchidanand Singh

Reputation: 1514

By using collections we can go for below code snippet - 

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

Upvotes: 0

Sri
Sri

Reputation: 4853

I recommend to use the hash-map (assuming no 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;
    }

Time complexity : O(n)

Space complexity : O(n)

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

Upvotes: 0

Rui Gon&#231;alves
Rui Gon&#231;alves

Reputation: 1375

Writing the previous answers in actual 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

Upvotes: 2

MAK
MAK

Reputation: 26586

(The question in its current form is a little confusing - my answer is assuming that the question is about finding two numbers in an array that sum to a given value)

Since the given array is unsorted, I am assuming that we are not allowed to sort the array (i.e. the given order of the array cannot be changed).

The simplest solution IMHO is to iterate over each number x and check if I-x occurs anywhere in the arrays. This is essentially what your O(n^2) solution is doing.

This can be brought down to O(n) or O(nlogn) by making the search faster using some sort of fast set data structure. Basically, as we iterate over the array, we query to see if I-x occurs 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 insert/lookup complexity of the set data structure that you use. A hashtable based implementation has a O(1) complexity so it gives you a O(n) algorithm, while a tree based set results in a O(nlogn) algorithm.

Edit:

The equivalent data structure to Python's set would be stl::set in C++ and TreeSet/HashSet in Java. The line I-x in seen would translate to seen.contains(I-x) in Java and seen.find(I-x)==seen.end() in C++.

Upvotes: -1

user unknown
user unknown

Reputation: 36229

I'm answering to "Finding duplicate element in an array?"

You search for i and j from 0 to < n, and later you check for 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;

Repeatedly setting dup=false is nonsense. Either dup is still false, or it was true, then you left the code with 'return'.

Upvotes: 3

Friedrich
Friedrich

Reputation: 5996

Sort the array (that can be done in the first O (n Log n) then the comparison just has to be done for the adjacent elements. Or just put the array into a hash table and stop if you find the first key with an exsting entry.

Upvotes: 6

Related Questions