KarmaAndCoding: Finding repeated elements in an array.

KarmaAndCoding: Finding repeated elements in an array.

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list.
The algorithm should run in linear time. (n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo.

Approach:

Let N = size of the input array A.

Now we need to find all the elements in the array which occur more than (N/K) times in the input Array A.

maintain a Map (Key=A[i], and value is the frequency of Key in array A so far).

as soon as the size of the Map reaches K, decrement the value of all the Keys by 1, if the value is 1, then after decrementing it will be 0 - Delete those keys from Map.

At max you will have to do (N/K) deletions. 

In the end you will be left with atmost (K-1) unique Keys - which are candidate answers.

Now again re-iterate through the array A and report the Keys whose frequency is greater than (N/K).

Time Complexity: O(nlogk).

space complexity: O(k).

Read full article from KarmaAndCoding: Finding repeated elements in an array.