How To 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 –
 
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 –
 
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).

Comments

Popular posts from this blog

How to change this to <%Html.ActionLink%> in my asp.net mvc application ?