first repeated element in an array???????

give an algo in o(n) to find first repeated element in an array?
e.g.{1,2,3,4,2,1,5,6}
output=2

giving it a try....

You can use Hash Tables.

in O(1) it will search the element present in the hash table and the moment any of it's entries list is appended for the first time you report that element as the first repeated element.

no idea about hash table
plz elaborate a li'l

yaar u can always search for hash tables on wikipedia, it's the idea that i have provided. and i think my idea is correct.

what about implementation of so called HASH TABLES??

not getting your point.. do you want me to implement the hash table??

Yaar implement kaise karoge ye batao.....
just dont giv the hint......

ok giving it a try...

From the domain of numbers specified, The hash table will be created(I don't exactly remember the process of creating a hash table) but it's from the domain of inputs from which it takes it's values.

Now having created your hash table, the values will be searched and inserted in O(1) time complexity.

Now the case arise that domain has repeated values(don't consider the domain of sets) so entering an existing value would create a problem(as it already exists), To overcome this problem a link is created to the value to be inserted like

1
2-2
3
4
5-5-5
and so on....
so when a link is created for the hash table for all the values,(that existed prior to the value that is being currently added) flag is raised denoting that a link has been created. The moment this is done for any value, report that to be as the first repeated element.

Correct me if wrong.....

Do U Know How MAP works in C++.
It must be using Some Hash Function ...
You Can Do It .. this way too..
But the point is .. Check Out If It searches in O(1) time..

I can't say about map... but for hash tables i m pretty much sure that it searches in O(1) time, if the element is present only once, and O(n) [n is the number of times the element is repeated] otherwise.