The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

The frequency of a Particular Element in an Array

The frequency of a particular element in an array is the number of occurrences of that particular element in the array (count). Consider the following array:

The array has 8 elements, from index 0 to 7 (zero based indexing). The frequency of 5 is 3 (count). The frequency of 2 is 4 (count). The frequency of 4 is 1 (count).

To determine the frequency of a particular element, just count the number of times that element occurs in the array. The following program illustrates this, for the number 5, then 2, and then 4 (read through the code and comments):

#include <stdio.h>

int oneElemFreq(int A[], int n, int no) {
    int count = 0;
    for (int i=0; i < n; i++)
        if (A[i] == no)
            count += 1;    //add 1 for each same element seen
            
    return count;
}

int main(int argc, char **argv) 
{   
    int arr[] = {5, 2, 4, 2, 5, 2, 5, 2};

    int N = sizeof(arr) / sizeof(arr[0]);    //length of array
      
    int freq5 = oneElemFreq(arr, N, 5);
    printf("Number of 5's is: %i\n", freq5);
    
    int freq2 = oneElemFreq(arr, N, 2);
    printf("Number of 2's is: %i\n", freq2);
        
    int freq4 = oneElemFreq(arr, N, 4);
    printf("Number of 4's is: %i\n", freq4);

    return 0;
}

The output is:

    Number of 5's is: 3
    Number of 2's is: 4
    Number of 4's is: 1

Number of Occurrences of every Element

The frequency of every element can be determine in two ways:

- the brute force way;
- using what is known as the frequency-of-occurrences or count array.

The Brute Force Way

In the brute force way, there are two nesting loops: the outer loop locates the next element in the given array. The inner loop counts the number of times that element occurs in the given array. For an element that occurs more than once, there will be repeated counting of that element in different inner loop iterations. That takes at least O(n²) time. The brute force way will not be addressed again in this chapter of the full course.

Using the Frequency of Occurrences Array

The frequency of occurrences array is also known as the count array. Under certain circumstances, it is known as the visited array.

Using the frequency of occurrences array leads to O(n + m) time, where n is the length of the given array and m is the length of the frequency of occurrences array.

When all the numbers in the given array are greater than or equal to zero (all positive), m is the biggest number in the given array. The length (size) of the frequency of occurrences array is actually m + 1, to account for zero as an element that might be occurring in the given array (see below).

The rest of this tutorial deals with the frequency-of-occurrences array.

Counting and using the Count of Every Element in the Given Array

Consider an unsorted array of integers such as,

There are eight elements (values) here. The highest value here is 16. The smallest value is 0. These are all positive integers. 0 is normally considered as a positive number. Each element here can be mapped to the index of another array as follows:

In this two-row table, the first row has the elements of the first (given) array, but in ascending order. This table represents the second array. Since the highest value in the first array is 16, there are 17 cells in the second array, indexed (numbered) from 0 to 16. The first extra cell in front in this second array, is to account for a possible value of 0, in the first (given) array. The second row in this second table shows the zero based indexes for the second array (index counting normally begins from 0 and not 1). In this second table, each value from the first array (table), is put just above its index (in the second array table).

Notice that there are some empty cells in the first row of this second table. Theses empty cells are for the numbers that are not found in the first array; as the second array has locations for possible first array values from 0 to 16, inclusive. If there were no 0 in the first array, its cell would still have been created in the second array, but left "empty".

The second array is usually longer than the first array, accounting for the values that would have been in the second array, but not found in the first array. The highest value in the first array is 16, and so the second array needs to have 17 cells, indexed from 0 to 16. In general, if the highest integer in the first array is m, then the second array needs to have m+1 cells, indexed from 0 to m.

The topic for this lesson (tutorial) is Counting Elements. The elements can be characters or strings, or some other similar entities, that are countable. It is the number of occurrences of each element in the first array, that is to be counted.

Notice that in the first array, there are 3 sevens, 2 zeros, 1 sixteen, 1 thirteen, and 1 four, giving 8 elements in total. This particular second table above is not really helpful, so far as counting the number of occurrences of each value in the first array, is concerned. It would have been better, if in the second table above, the number of occurrences of each number was put just above its index for the second array.

That is, instead of putting 7 above the index 7, 3 should have been put, as 7 occurs three times in the first array. Instead of putting 0 above index 0, 2 should have been put since 0 occurs two times, in the first array. Instead of putting 16 above index 16, 1 should have been put since 16 occurs one time. Instead of putting 13 above index 13, 1 should have been put, since 13 occurs one time. Instead of putting 4 above index 4, 1 should have been put, since 4 occurs one time. The following table or array, should be used instead of the above second table:

This third table can be arrived at without passing through the second table (or second array) above. There are no empty cells this time. Instead of an empty cell, 0 is put to indicate that the expected value from the first table, occurred 0 time. In other words, the new array is still given a length of m+1, indexed from 0 to m, and each cell has the number of occurrences of its index in the first array, as value. The index that did not occur in the first array as value, is given the cell value of 0, to mean zero occurrence, in this third (new) array.

Counting Number of Occurrences of each Element in a Given Array

A function can be written to return or display a (new) array that has the count of each element in a given array (without passing through the second array above). This return array is the new or third (count) array in the above section. Let the given array be

and be called array A. There are 8 elements in the given array. Let the frequency-of-occurrences array to be returned be called, count. The maximum integer in the given array is 16. So count needs to have 16+1 = 17 elements, to account for possible 0’s in the given array; though this given array has no 0. The return array, count for this case, would be:

The number of occurrences of each number in a given array, can be counted in two ways: the blunt (brute force) way, or by incrementing from zero, the value in the count array, each time its index is encountered in the given array, as the given array is scanned, once.

It can be cumbersome to produce the count array by counting the blunt or brute force way. So only the smart way (incrementing each integer value in the count array appropriately, from 0) is explained, as follows:

First, the count array is created with all the cells initialized to 0. Next the given array is scanned from its beginning (to the end). For each value (integer) read in the given array, the index in the count array that is the same as the value read, has its own cell value (number of occurrences) incremented by 1.

At the end, the count array is read out (returned). For a value that does not exist in the given array, its count in the count array remains at zero. For any value that exists in the given array, its count in the count array, is the number of places (occurrences) in which it is found in the given array.

It takes m = 16+1 approximate operations to create and initialize the count array with zeros. It takes n = 8 main operations to scan the given array, doing all the necessary increments (adding 1 each time) to the values of the count array, according to whose indexes are encountered in the given array. This gives a time complexity for the function, as O(n+m).

The program is (read through the code and comments):

#include <stdio.h>

void countFrequencies(int A[], int n, int m) {    
    int count[m+1];
    for (int i=0; i < m+1; i++ )
        count[i] = 0;      //time complexity: m operations
        
    for (int i=0; i < n; i++)  //time complexity: n operations
        count[A[i]] = count[A[i]] + 1;  //add 1 to whatever is already in the count cell
            
    for (int i = 0; i < m+1; i++) 
        printf("%i, ", count[i]);
    printf("\n"); 
}

int main(int argc, char **argv) 
{   
    int A[] = {16, 7, 3, 7, 13, 7, 3, 4};

    int n = sizeof(A) / sizeof(A[0]);    //length of given array
    
    int m = 0;  //maximum number (value) in given array
    for (int i = 0; i < n; i++)  //looking for actual maximum number in A
        if (A[i] > m)
            m = A[i];
                
    countFrequencies(A, n, m);

    return 0;
}

The output is:

    0, 0, 0, 2, 1, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 1, 

as expected. In the statement,

        count[A[i]] = count[A[i]] + 1;

A[i] is the i^th element in the given array. It is an integer. This integer becomes an index in the count array.

The maximum value for the given array is determined in the calling function area in the program; and that sequence of operations should not be included in the time complexity.

The time complexity for the whole program is actually O(2n+2m). One n is in the calling function area to look for the maximum value in the given array of n elements. The other n is in the called function to produce the non-zero values of the count array. One m is for the initialization of all the values of the count array to zero, in the called function. The other m is still in the called function to print all the values in the count array. However, the coefficient (multiplicand of 2) is usually omitted to quote the time complexity as O(n+m).

The space complexity is O(n+m). Here, n is for the input array and m is for the count array. Any temporary space is ignored. The big-O notation for time and space complexity are estimates, though the maximum possible number is usually chosen.

Issue with Negative Numbers

Notice that in the given array above, there is no negative number. The count array (or any array) does not have a negative index; and so when the given array has negative integers, there is a problem. This problem can be resolved in two ways: 1) adding a big number to all the values in the given array, so that all the resulting numbers are greater or equal to 0, ending up with a mapped array; or 2) separating the given array into one array for negative numbers and one array for positive numbers (zero being positive, and with the array for positive numbers).

Adding a Big Value to have all Numbers Positive

Assume that the list (array) with negative numbers, for which multiple occurrences of each number is to be counted, is:

This given array will have to be scanned to get both the lowest negative value and the highest positive value. Both the lowest and highest negative values can be obtained in one for-loop. That takes O(n) time. In the above array, the lowest value (negative) is -6, and the highest (positive) is +16.

So if 6 is added to each integer, the -6 will be translated to 0, -2 will be translated to 4, -1 will be translated to 5, 0 will be translated to 6, 4 will be translated to 10, and so on. 16, the highest value will be translated to 22. The translation process needs an additional O(n) time. After the translation, the following array results:

With the highest value of 22, there should be 22 + 1 = 23 cells in the count (new) array. In O(m) time, where m = 23, the count array becomes:

In order to return or report the count array, the 6 added to each value has to be removed. This takes an additional O(m) time. The return count array, becomes:

This should be returned as a two-dimensional array, instead of a one-dimensional array. With that, one way of the counting of multiple occurrences, with negative values, is done!

Separating Given array into Negative and Positive arrays

Let the given array be:

Consider zero as a positive number. In separating this array into one with negative values and another with positive values, the minimum negative value, the maximum negative value, the minimum positive value, and the maximum positive value, can also be found. All that can be done in one scan. The number of elements in either resulting arrays can also be determined in this same pass. When there are many such operations in one step (body of for-loop), the time for the one scan, may become O(n.log₂(n)) approximately, and not just O(n).

Imagine that there was only one operation in one step (the for-loop body), then in one scan of n elements, the time would be O(n), equivalent to one scan. Assume that n = 8. If there are two operations in one step, the time would be O(8) x 2, equivalent to two scans. If there are 3 operations in one step, the time would be O(8) x 3, equivalent to 3 scans, and generalized as O(n.log₂(n)). Remember that log₂(8) = 3.

Since the O(n.log₂(n)) time for the problem at hand, is not even part of the solution, it should be done (coded) in the calling function area of the program. The resulting arrays from the given array above will be:

and

The arrangement of negative values in descending order here, is coincidental.

There will be two count arrays: one for the negative values and one for the positive values. The number of elements in either array should be known.

The smallest value in the array with negative values above, is -6. The biggest value in this array is -1. In the corresponding count array, where the indexes are all positive, -6 corresponds to index 0. The count array is:

The number of elements in this count array is the maximum negative value minus the minimum negative value, plus 1. Zero index is there.

The count array for the positive numbers is done as in the first (normal) case above (where m+1 = 16+1). It is:

The two count arrays are returned separately.

Visited Array

The visited array is the same as the Frequency of Occurrences Array. However, in some cases, the visited array may consist of just true or false. True means the element occurs in the given array at least once; False means the element does not occur in the given array at all.

After Establishing the Frequency of Occurrences Array

Do not forget that the Frequency of Occurrences Array is also called the Count Array or the Visited Array.

After establishing the Frequency of Occurrences Array, there are usually two options: Either

- address (iterate over) the Frequency of Occurrences Array alone without addressing the given array, OR
- address (iterate over) the given array in conjunction with the Frequency of Occurrences Array.

Given Array without Whole Numbers

The above explanation essentially deals with a given array of whole numbers. If the given array consists of characters or strings, the frequency of each element can still be determined. In this case, a hashmap has to be used in the place of the count array - see later.

A hashmap is still much better than two count arrays, if the given array has negative integers.

Thanks for reading.