find first repeated element..

Question

given an array of n element, what will be the time complexity to find 1st repeated element when array have more than one repeated elements??

Answer 1

$O(n)$

Algorithm:

int count(int a[],int n){
    int count[10];
    for i=1 to 10:
        count[i]=0;
    for  i = 1 to n{
        k = count[a[i]]++;
        if (k>1) 
            return  a[i];
    } 
    return 0;
}

Comments

that 1st no which involve in repetition not asking no that envolve in repetition and as soon as detected..

---

You assumed that all the elements in the array are between 0 and 9. The question doesn't mention that, and you can't simply assume it because assuming it completely changes the problem.

---

that can be done by just increasing the size of array count ....but that will not affect  the time complexity.I have declared the size of count =10 because range of no is not specified in the  ques.

Answer 2

It will be O(n)

Insert one by one each element in a hash table and whenever first collision will occur that key or element will be the first one to repeat. Since it can go upto n elements.. So O(n).. Space complexity O(n).

Comments

yaa O(n) right but what u say when constraints or given on space is O(1)

---

The complexity of Hashing is O(n) in the worst case. You can't assume perfect hashing.

Answer 3

From a theoretical point of view, it will take $O(n \log n)$ time in the worst case. It can be done by sorting the array and then sequentially searching for any adjacent elements that are equal.

Note: The problem doesn't mention any bound on the elements of the array. The elements can be as large as wanted, and need not be integers! Assuming that the elements are bounded (as in Saurav's answer) or that the elements hash to unique locations (as in Sonu's answer) completely changes the problem.

---

Practically, you will always have a bound on the elements. If the bound is sufficiently small ($<32$ bits, for example), Saurav's answer will be efficient (if the $n\gg2^{32}$). Or you could have a hash function that provides unique hashes for all practical purposes. Then Sonu's answer would be the better way to go.