# Find distinict elements in an array in $O(n)$ time

Given this pseudo-code that finds the number of distinct elements in the given array:

D(A) // A is an array of numbers
U_Size = 1
For i=2 to length(A)
U=?
For j=1 to U_Size
If A[j]=A[i]
Then U = FALSE
j = U_Size
if U = TRUE
Then U_Size = U_Size +1
A[U_Size] = A[i]
return U_Size


Time complexity for that alogrithm is $$O(n^2)$$

I will need to write 2 new algorithms for the same purpose in $$O(n)$$ according to one of each of the conditions bellow:

1. let's say that the numbers are integers only and inside the range of [$$10,10n$$], without using any sorting method
2. Now, there is no given range of numbers, and I can use any sorting method I want

MY SOLUTION:

for the first condition, I tried using HashSet, but I think it has a more sofisticated solution. My pseudo-code:

countDistinctNums(int A[], int n)
hashSet hs = new Hashset
for i=0 to n
// add all the elements to the HashSet

// return the size of hashset as it consists of
// all unique elements
Return hs.size();


for the second one, a hash table will be the optimal solution but I think also one of the linear-sorting methods will be good enough

My questions are:

1. Does HashSet is a good solution for one of the conditions ( or both )?
2. How do I implement an HashTable for the solution of the second condition?

For the first task you can use a solution similar to yours. Let the input array be $$A[1, \dots n]$$. Create an array $$B$$ indexed with the integers from $$10$$ to $$10n$$ where each entry is a boolean value initially set to false. Then, for each input element $$A[i]$$, set $$B[A[i]]$$ to true. At the end of the above loop, return the number of indices $$y$$ such that $$B[y]$$ is true. This runs in $$O(n)$$ worst-case time.

Notice that, depending on how the hashtable is implemented, a hashtable-based solution is not guaranteed to have a worst-case time complexity of $$O(n)$$. Usually the hash-tables provided by the common programming languages only provide you with expected constant time operations.

Also, if don't have any other information on the values the the input integers, you can't use linear-time sorting algorithms (since their complexity depends on the range of the input values).

Anyway, your solution already works for the general problem in $$O(n)$$ expected time.

I don't think the general problem can be solved in $$O(n)$$ worst-case time. According to Wikipedia, there is a lower bound of $$\Omega(n \log n)$$ on the algebraic decision tree model, and randomness doesn't help.

• Sorry, but I did not understand the first paragraph implementation. What do you mean by: "for each input element $x$, set $A[x]$ to true" ? pseudo-code will be helpful too :) – Omri Braha May 13 at 12:00
• Is it clearer now? – Steven May 13 at 12:04
• Yes, thank you! – Omri Braha May 13 at 12:12

You can solve the second task with $$O(n)$$ expected running time (average-case running time), if you use a hash table with a 2-universal hash function. As far as I know, no deterministic $$O(n)$$-time algorithm is known.

• Can you elaborate on Universal hash function? – Omri Braha May 14 at 8:38