Count frequencies of all elements in array in O(1) extra space and O(n) time

Given an unsorted array of n integers that can contain integers from 1 to n. Some elements can be repeated multiple times and some other elements can be absent from the array. Count the frequency of all elements that are present and print the missing elements.

Examples: 

Input: arr[] = {2, 3, 3, 2, 5}
Output: Below are frequencies of all elements
        1 -> 0
        2 -> 2
        3 -> 2
        4 -> 0
        5 -> 1
Explanation: Frequency of elements 1 is 
0, 2 is 2, 3 is 2, 4 is 0 and 5 is 1.
 
Input: arr[] = {4, 4, 4, 4}
Output: Below are frequencies of all elements
        1 -> 0
        2 -> 0
        3 -> 0
        4 -> 4
Explanation: Frequency of elements 1 is 
0, 2 is 0, 3 is 0 and 4 is 4.

Simple Solution 

• Approach: Create an extra space of size n, as elements of the array is in the range 1 to n. Use the extra space as HashMap. Traverse the array and update the count of the current element. Finally, print the frequencies of the HashMap along with the indices.
• Algorithm: 
  1. Create an extra space of size n (hm), use it as a HashMap.
  2. Traverse the array from start to end.
  3. For every element update hm[array[i]-1], i.e. hm[array[i]-1]++
  4. Run a loop from 0 to n and print hm[array[i]-1] along with the index i

Implementation:

Below are counts of all elements
1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1

Below are counts of all elements
1 -> 1

Below are counts of all elements
1 -> 0
2 -> 0
3 -> 0
4 -> 4

Below are counts of all elements
1 -> 3
2 -> 0
3 -> 2
4 -> 0
5 -> 2
6 -> 0
7 -> 2
8 -> 0
9 -> 2
10 -> 0
11 -> 0

Below are counts of all elements
1 -> 0
2 -> 0
3 -> 11
4 -> 0
5 -> 0
6 -> 0
7 -> 0
8 -> 0
9 -> 0
10 -> 0
11 -> 0

Below are counts of all elements
1 -> 1
2 -> 1
3 -> 1
4 -> 1
5 -> 1
6 -> 1
7 -> 1
8 -> 1
9 -> 1
10 -> 1
11 -> 1

Below are counts of all elements
1 -> 1
2 -> 1
3 -> 1
4 -> 1
5 -> 1
6 -> 1
7 -> 1
8 -> 1
9 -> 1
10 -> 1
11 -> 1

• Complexity Analysis: 
  • Time Complexity: O(n). 
    As a single traversal of array takes O(n) time.
  • Space Complexity: O(n). 
    To store all the elements in a HashMap O(n) space is needed.

Below are two Efficient methods to solve this in O(n) time and O(1) extra space. Both methods modify the given array to achieve O(1) extra space.

Method 2: By making elements negative. 

• Approach: The idea is to traverse the given array, use elements as an index and store their counts at the index. Consider the basic approach, a Hashmap of size n is needed and the array is also of size n. So the array can be used as a hashmap, all the elements of the array are from 1 to n, i.e. all are positive elements. So the frequency can be stored as negative. This might lead to a problem. Let i-th element be a then the count should be stored at array[a-1], but when the frequency will be stored the element will be lost. To deal with this problem, first, replace the ith element by array[a-1] and then put -1 at array[a-1]. So our idea is to replace the element by frequency and store the element in the current index and if the element at array[a-1] is already negative, then it is already replaced by a frequency so decrement array[a-1].

• Algorithm: 
  1. Traverse the array from start to end.
  2. For each element check if the element is less than or equal to zero or not. If negative or zero skip the element as it is frequency.
  3. If an element (e = array[i] – 1 ) is positive, then check if array[e] is positive or not. If positive then that means it is the first occurrence of e in the array and replace array[i] with array[e], i.earray[i] = array[e] and assign array[e] = -1. If array[e] is negative, then it is not the first occurrence, the update array[e] as array[e]– and update array[i] as array[i] = 0.
  4. Again, traverse the array and print i+1 as value and array[i] as frequency.
• Implementation:

Below are counts of all elements
1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1

Below are counts of all elements
1 -> 1

Below are counts of all elements
1 -> 0
2 -> 0
3 -> 0
4 -> 4

Below are counts of all elements
1 -> 3
2 -> 0
3 -> 2
4 -> 0
5 -> 2
6 -> 0
7 -> 2
8 -> 0
9 -> 2
10 -> 0
11 -> 0

Below are counts of all elements
1 -> 0
2 -> 0
3 -> 11
4 -> 0
5 -> 0
6 -> 0
7 -> 0
8 -> 0
9 -> 0
10 -> 0
11 -> 0

Below are counts of all elements
1 -> 1
2 -> 1
3 -> 1
4 -> 1
5 -> 1
6 -> 1
7 -> 1
8 -> 1
9 -> 1
10 -> 1
11 -> 1

Below are counts of all elements
1 -> 1
2 -> 1
3 -> 1
4 -> 1
5 -> 1
6 -> 1
7 -> 1
8 -> 1
9 -> 1
10 -> 1
11 -> 1

• Complexity Analysis: 
  • Time Complexity: O(n). 
    As a single traversal of the array takes O(n) time.
  • Space Complexity: O(1). 
    Since no extra space is needed.

Method 3: By adding ‘n’ to keep track of counts.

• Approach: All the array elements are from 1 to n. Reduce every element by 1. The array elements now are in range 0 to n-1 so it can be said that for every index i, floor(array[i]/n) = 0. 
  So as previously said that the idea is to traverse the given array, use elements as an index and store their counts at the index. Consider the basic approach, a Hashmap of size n is needed and the array is also of size n. So the array can be used as a hashmap but the difference is that instead of replacing elements add n to the array[i]th index. 
  So after updating the array[i]%n will give the ith element and array[i]/n will give the frequency of i+1. 

• Algorithm: 
  1. Traverse the array from start to end and reduce all the elements by 1.
  2. Again traverse the array from start to end.
  3. For each element array[i]%n update array[array[i]%n], i.e array[array[i]%n]+n
  4. Traverse the array from start to end and print i + 1 as value and array[i]/n as frequency.
• Implementation:

1 ->  0
2 ->  2
3 ->  2
4 ->  0
5 ->  1

• Complexity Analysis: 
  • Time Complexity: O(n). 
    Only two traversals of the array are needed and a single traversal of the array takes O(n) time.
  • Space Complexity: O(1). 
    Since no extra space is needed.