Codility - Distinct

Solution to Codility lesson4-exercise3 Distinct problem, link to Codility problem and complete solution at the end of the post.

Definitions:
\mathbf{A} = \{x \in \mathbb{Z}\ |-1,000,000\leq x \leq 1,000,000\land |A| = M \},\mathbf{A}\, is\, a\, multiset.
\{N \in \mathbb{N}\ |\ 0\leq N \leq 100,000\}

Problem:
Define a function solution with input A , such that solution returns the number of distinct values in array A.

  • Expected worst-case time complexity is O(N*log(N));
  • Expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified. 

Analysis:

To solve this problem, first we have to sort A, with the array sorted we jut have to visit every element of A.
If has no element the result is 0, otherwise we have at least one distinct element.

Since we already counted the first distinct element, now we search for a different one, and every time we find an element that is different from its predecessor we add one to the result.

Visiting every element of gives us a time complexity of O(N). The sort function in Python gives us O(N*log(N))
Then the total time complexity will be O(N) + O(N*log(N)),  which is O(N*log(N)).
For the space complexity we have O(1).

Complete Solution:

Time Complexity O(N *log(N))
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/