Codility - Lesson 8 Leader

Source Link:
https://codility.com/programmers/lessons/8-leader/

Some Notes: 
Let us consider a sequence a0, a1, . . . ,an≠1. The leader of this sequence is the element whose value occurs more than n/2 times.

 

In the picture the leader is highlighted in gray. 

The leader may be found in many ways. If there is no leader, the result should be -1.


8.2. Solution with O(n log n) time complexity

Having sorted the sequence, we can easily count slices of the same values and find the leader in a smarter way. Notice that if the leader occurs somewhere in our sequence, then it must occur at index n/2 (the central element).

8.2: Leader — O(n log n).
1 def fastLeader(A):
2 n = len(A)
3 leader = -1
4 A.sort()
5 candidate = A[n // 2]
6 count = 0
7 for i in xrange(n):
8 if (A[i] == candidate):
9 count += 1
10 if (count > n // 2):
11 leader = candidate
12 return leader


8.3. Solution with O(n) time complexity

Removing pairs of different elements is not trivial.

Note: we may use "HashMap" instead (for counting).