Calculate frequency of all elements present in an array of specified range in linear time and using constant space

Given an unsorted array of integers whose each element lies in range 0 to n-1 where n is the size of the array, calculate the frequency of all elements present in the array in linear time and using constant space.

 

For example,


Input:  { 2, 3, 3, 2, 1 }

Output:

Element 1 appears 1 times
Element 2 appears 2 times
Element 3 appears 2 times

 

 
Simple solution is to use a count array. We traverse through the given array and update frequency of each element in count array. Finally after all array elements are processed, we iterate through the count array to print frequencies. We can also use map instead of count array but using map do not take advantage of the fact that array elements lies between 0 to n-1.

 
C/C++ implementation –
 

C

Download   Run Code

C++

Download   Run Code

Output:

Element 1 appears 1 times
Element 2 appears 2 times
Element 3 appears 2 times

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

 
We can also solve this problem without using any extra space by taking advantage of the fact that array elements lies in the range 0 to n-1. For each element A[i] present in the array, we increment value present at index (A[i] % n) by n. Finally, we traverse the modified array and if A[i] is more than or equal to n, then i appears in the array (A[i]/n) times.

For example, consider array {2, 3, 3, 2, 1}. After incrementing value present at index (A[i] % n) for each element A[i] by n, the array becomes {2, 8, 13, 12, 1}. Now if we take (arr[i]/n) for each index i, we get {0, 1, 2, 2, 0}. Here, A[i] denotes the frequency of index i.

 
C implementation –
 

Download   Run Code

Output:

1 appears 1 times
2 appears 2 times
3 appears 2 times

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Exercise: Modify the program if array elements lies in range 1 to n

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of