Time complexity for element repetition in array

Question

Given an array of n random numbers, find a O(n*ln n) algorithm to check if it contains repetitive occurrences of some number using only arrays (no other complex data structures).

I got the obvious O(N*N) when you take each element and compare with the rest to check for a match. You can also sort it and compare adjacent elements in n*log n. I am looking for something other than that.

Answer 1

OK, Let me have a take on this.

1. Find the largest element(say max) in the array. (O(N) operation)
2. Create a boolean array(say temp) of size max.
3. Traverse through the original array and use the current_value as index for temp array and check if it is true i.e. if (temp[current_value] == true)
4. If it is true you have found the repeating element else set temp[current_value] = true

Obviously this algorithm is not space efficient as we don't know what would be the size of the temp array and most of the spaces in the temp array would never be visited but it's time complexity is O(N)

Answer 2

It's better to replace the array with a hash table.Then, there is no need to find min/max, just start putting your numbers in the hash table as kyes, checking before each "put" whether that key is already there. Note that the array approach cannot handle numbers in a large range, say min=-2^63, max=2^63, even if there are just a few of them. On the other hand, hash table can handle them easily.

However, I just noticed that you want to use only arrays. Then you can simulate the hash table using the array. For details see here: http://algs4.cs.princeton.edu/34hash/ You can select a simple hash function and handle collisions a simple way, for example by putting a collided value into the next available array slot.