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

Problem

You are given an array A consisting of positive integers.
Return the total frequencies of elements in A, such that those elements all have the maximum frequency; in two solutions: O(n+m) and O(n) times. The frequency of an element is the number of occurrences of that element in the array.

Example 1:
Input: A = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array. So the number of elements in the array with maximum frequency of 2 is 4.

Example 2:
Input: A = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency of 1 is 5.

Constraints:

    1 <= A.length <= 100    //size of array
    1 <= A[i] <= 100

A) Use the frequency-of-occurrences scheme for a called function of O(n+m) time.
B) Produce the same result in one complete iteration (one pass).

Note: There can be more than one same maximum frequency for different elements in the array, as in the examples above. The return value is effectively the sum of this same maximum frequency. The sum of the different same frequencies, gives the total number of different elements concerned. If there is only one maximum frequency, just return that frequency.

A) O(n+m) Time Solution

The algorithm is as follows:

- Iterate over the given array while producing the count (frequency-of-occurrences) array.
- Iterate over the count array (not the given array), to obtain the sum of same maximum frequencies.

While iterating over the count array, there should be two variables, which are: maximum-frequency and sum-of-maximum-frequencies (same). Of course, as the count array is iterated over, at the beginning, the first frequency is assigned to the maximum-frequency variable and also assigned to the sum-of-maximum-frequencies variable. If any higher frequency is encountered, both these variables are reset. If a frequency is encountered that is the same as the reset values, then the sum-of-maximum-frequencies variable is incremented by maximum-frequency while the maximum-frequency variable remains the same. This resetting of the two variables or incrementing of the sum-of-maximum-frequencies variable by maximum-frequency, continues till the end of the count array.

The final value for the sum-of-maximum-frequencies variable will be the answer, which is the total of all the different elements that have the same maximum-frequency of occurrences.

The O(n+m) Time Program

The O(n+m) time solution is (read through the code and comments):

#include <stdio.h>

int totElemMaxFreq(int A[], int n, int m) { 
    int count[m+1];
    for (int i=0; i < m+1; i++)
        count[i] = 0;    //initializing count array
        
    //give frequencies to count array
    for (int i=0; i < n; i++)
        count[A[i]] = count[A[i]] + 1;

    int maximum_frequency = 0; 
    int sum_of_maximum_frequencies = 0;
    
    for (int i=0; i < m+1; i++) {
        if (count[i] == maximum_frequency) 
            sum_of_maximum_frequencies = sum_of_maximum_frequencies + maximum_frequency ;

        if (count[i] > maximum_frequency) {    //reset
            maximum_frequency = count[i];
            sum_of_maximum_frequencies = count[i];
        }
    }
    
    return sum_of_maximum_frequencies;
}

int main(int argc, char **argv) 
{   
    int A1[] = {1,2,2,3,1,4};
    int n1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int m1 = 0;    //for max number in A1
    for (int i=0; i < n1; i++)
        if (A1[i] > m1)
            m1 = A1[i];
    int ret1 = totElemMaxFreq(A1, n1, m1);
    printf("%i\n", ret1);
    
    int A2[] = {1,2,3,4,5};
    int n2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int m2 = 0;    //for max number in A1
    for (int i=0; i < n2; i++)
        if (A2[i] > m2)
            m2 = A2[i];
    int ret2 = totElemMaxFreq(A2, n2, m2);
    printf("%i\n", ret2);

    return 0;
}

The output is:

    4
    5

The official time complexity for the called function is O(n+m), with n for iterating over the given array and producing the count array, and m for iterating over the count array and producing the total of the maximum frequencies. The time to initialize the count array to 0's is ignored.

The space complexity for the called function is O(n) for the given array. The O(1) space complexities for the maximum_frequency and sum_of_maximum_frequencies variables are ignored.

A) O(n) Time Solution

In the above solution, after the count array of frequencies has been produced, the count array is iterated over, while the maximum-frequency and sum-of-maximum-frequencies variables are reset from time to time, and the sum-of-maximum-frequencies variable incremented by maximum-frequency, independently.

As the count array of frequencies is being produced, maximum-frequency and sum-of-maximum-frequencies variables can still be updated in the same way. The main difference now is that these variables will be updated more often, since the frequency of each element is not yet fixed at its upper limit, until the complete scan of the given array. Note that the count array still needs to be produced, but it will not be iterated over. In that way, the algorithm will take O(n) time, where n is the time to iterate over the given array.

When the frequency for an element is increased by 1, the two variables are addressed (updated).

The O(n) Time Program

The O(n) time solution is (read through the code and comments):

#include <stdio.h>

int totElemMaxFreq(int A[], int n, int m) { 
    int count[m+1];
    for (int i=0; i < m+1; i++)
        count[i] = 0;    //initializing count array

    int maximum_frequency = 0; 
    int sum_of_maximum_frequencies = 0;
    
    //give incrementing frequencies to count array 
    //as well as updating maximum_frequency and sum_of_maximum_frequencies
    for (int i=0; i < n; i++) {
        count[A[i]] = count[A[i]] + 1;
        
        if (count[A[i]] == maximum_frequency) 
            sum_of_maximum_frequencies = sum_of_maximum_frequencies + maximum_frequency ;

        if (count[A[i]] > maximum_frequency) {    //reset
            maximum_frequency = count[A[i]];
            sum_of_maximum_frequencies = count[A[i]];    
        }
    }
    
    return sum_of_maximum_frequencies;
}

int main(int argc, char **argv) 
{   
    int A1[] = {1,2,2,3,1,4};
    int n1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int m1 = 0;    //for max number in A1
    for (int i=0; i < n1; i++)
        if (A1[i] > m1)
            m1 = A1[i];
    int ret1 = totElemMaxFreq(A1, n1, m1);
    printf("%i\n", ret1);
    
    int A2[] = {1,2,3,4,5};
    int n2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int m2 = 0;    //for max number in A1
    for (int i=0; i < n2; i++)
        if (A2[i] > m2)
            m2 = A2[i];
    int ret2 = totElemMaxFreq(A2, n2, m2);
    printf("%i\n", ret2);

    return 0;
}

The output is:

    4
    5

The principal for-loop iterates from 0 to n and not 0 to m+1. Note the use of count[A[i]], all over, in the principal for-loop.

The official time complexity for the called function is O(n), with n being for iterating over the given array and producing the count array, and also producing the total of the maximum frequencies. The time to initialize the count array to 0's is ignored.

The space complexity for the called function is O(n) for the given array. The O(1) space complexities for the maximum_frequency and sum_of_maximum_frequencies variables are ignored.

Thanks for reading.