Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

Objective: Given an array of size of N and number k. Find all elements in an Array which appears more than N/K times.

Input: Array [] and number k.

Example:

int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 };

K = 4

N/k = 14/4 = 3

Output will be [3,4] they appear 5, 4 times respectively.

Approach:

Naive Approach: Take two for loops , check every element with all other elements, Time Complexity –   O(n2) time.

Better Approach: Tetris Game technique- O(Nk)

  • We will create a class structure which will store an element and its count.
class Elements{
   intelement;
   intcount;
   public Elements(int element, int count){
   this.element = element;
   this.count =count;
  }
}
  • Create array etms[] contains k-1 objects of class Elements with element =0 and count = 0.
  • So idea is, navigate all the elements of given array.
  • Check if element exist in etms[] if not, insert it with the count 1 and if exist then increase its count.
  • Also check if etms[] gets full when inserting an element, if it is not, follow the previous step. If it is full then reduce the count of every existing element in the etms[]. (Just think of a Tetris game, when row gets full, it gets deleted and size of the Tetris reduced by 1) see the picture below.
  • Once all the elements of array gets over, check every element of etms[] with array and print those elements which has N/K times.
Find All Elements in an Array which appears more than NbyK times

Find All Elements in an Array which appears more than NbyK times

Complete Code:


Output:

4 appears more than n/4 times, Actual count is 5
3 appears more than n/4 times, Actual count is 4

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • cabhishek

    Why not use hashmap to store the count ?

    • tutorialhorizon

      You can use the Hashmap , if you are storing all the elements in hashmap then it will take O(n) space. you can apply the same logic which is mentioned in the post with hash map size k-1, then space complexity will be O(k-1)

  • Amarnath

    Good logic.
    I have a question, in the above chart’s last step 8 has 1, 4 has 3, 3 has 2. As per logic we will look at the count of all the elements and the elements which are having >= N/K = 14/4 = 3 will be the result. Here the count of element 4 is having count >= 3. Hence this should be the answer. But why is 3 also part of the result? Since element 3 has count only 2, it should not be added in the result right?

  • Ankita

    Thank you so much for the diagram !! It made understanding this algo a lot easier 🙂
    Also, the code is very clean.

  • ayushi garg

    how do you optimise if the array is sorted?

    • tutorialhorizon

      If array is srsort then problem will become trivial ..all the repeated elements will be together. So problem will be solved in single iteration. Do the iteration and keep track of the count of current element and if count is greater than n/k print it , and as element changes , reset the counter to 0

      • ayushi garg

        Just found out that you can do it in O(klogn). Algo is:
        Take elements at i*n/k positions for all possible candidates.
        Then for each of those elements, find their first and last occurrence. This step takes log(n) time. Can be done by tweaking binary search.
        Then report the elements whose frequency meets the threshold.

%d bloggers like this: