4 Ways To Count Frequency Of Each Element In An Array (+Examples)
C++ programming language provides us with many data structures for data storage and processing. An array is one of the most used fundamental data structures that allow the collection of elements having the same data type. While working with elements in an array, we often need to analyze and process the data they contain.
In this, the count frequency of each element in an array method is the most basic way of determining the number of times each unique element appears in an array. It provides valuable insights about data distribution and helps to detect patterns and frequency counts or densities that can be used in data analysis and statistical calculations.
In this article, we will have a detailed discussion of the 4 methods used to count the frequency of each element in an array.
To begin with, consider an unsorted array whose element frequency is to be found. Now to find the frequency of each element in the array, we can use multiple methods, including using loops, space optimization, sorting, etc. We have discussed each of these in detail, with the help of examples in multiple languages.
Count Frequency Of Each Element In An Array Using Two Loops
First, we will try to employ a basic method to count the frequency of each element in an array. In this method, we will make use of two for loops along with if-statements. The outer loop will be used as a pointer to each element, and the inner loop will be used to count the occurrence of the element pointed by the outer loop.
We will also create and use a new vector (of data-type bool) that keeps track of the duplicate elements that have been counted already. (We can also use an array of type boolean)
Task Given: Count the frequency of each element in an array of the given array.
Array Given:
array[] = { 2, 4, 2, 7, 8, 4, 7, 2, 2, 4}
C++ Code:
Output:
Element Frequency
2 4
4 3
7 2
8 1
Explanation:
We begin the above C++ program by including the important library and using namespace.
- We then define a Freq_count() function, which takes the integer array and the integer variable, num, as inputs.
- Inside the function, a boolean vector, Visited, and the outer for loop is initiated. The for loop iterates/ points to each element of the array, and the bool vector keeps track of the duplicate elements.
- Using the if statement, we determine that if the element is already visited, then the program jumps to the next element. If not visited, then a new count variable is count is initialized, as mentioned in the comment.
- Now the inner loop starts traversing from the next element till the end of the array. If an element matches with the element pointed by the outer loop, then the element at that index in the vector is made true, and the count is increased.
- Hence the Frequency count of each element is increased by 1 and printed accordingly. This way, the function counts the frequency of each element in the array.
- Next, in the main function, we declare and initialize an integer array and define num to find the length of the array using the sizeof() operator.
- We then call the Freq_count() function and pass num and array to the function as inputs.
- The output is printed to the console using cout, and the program terminates with return 0.
Complexity Analysis:
Time Complexity - O(n2), since it uses a nested loop structure
Space Complexity - O(n), since we need a new vector of length n
Java Code:
Python Code:
Using Hash Map To Count Frequency Of Each Element In An Array
Hash map in C++ is a data type that provides an efficient way of storing a key and the respective element as a pair. Here, the key and the element can be of any data type. Similarly, we can use a map of unordered type to store the frequency count of each element along with a respective element as the key.
So, the element is used as a key, and then we find the frequency of each element in an array which is then updated in the element frequency pair of the hash map. Let’s understand this with the help of the code sample solution given below, along with a step-by-step explanation of the same.
Task Given: Count the frequency of each element in an array given.
Array Given:
array[] = { 2, 4, 2, 7, 8, 4, 7, 2, 2, 4}
C++ Code:
Output:
8 1
7 2
4 3
2 4
Explanation:
- We begin by defining a function, frequency_count, which takes an array and integer variable length as inputs.
- Inside the function, we declare an unordered map (or Hash map), freq_map, of integer pairs with the element as the key and the other integer as frequency.
- We also initiate two for-loop where the first loop traverses through each element of the array. If the element we are looking for is not present in the map, then we insert it along with the frequency equal to 1.
- If it is already present, then we increase the frequency count by 1. The second loop uses cout along with auto and iterator, itr, to print the element on the console.
- Then in the main function, we declare and initialize an integer array which will act as the first input to the frequency_count function.
- Also, the integer variable, length, is used to find the size of the array using the sizeof() operator. This acts as the second input.
- Both these inputs are passed to the frequency_count function, which, when invoked, prints the output to the console.
Complexity Analysis:
Time Complexity - O(n), since it uses only one loop.
Space Complexity - O(n), since we need a new map of size O(2n) for n keys and respective frequency counts approximating to O(n).
Java Code:
Python Code:
Sorting An Array To Count Frequency Of Each Element
In this approach, the array is first sorted, and then a single loop is used to count the frequency of each element. While traversing the sorted array, the frequency of each element is counted by checking if the current element is equal to the next element. This method has a time complexity of O(n log n) due to the sorting step, where n is the number of elements in the array. While it is not as efficient as the hash map method, it might still be better than the two-loop approach. Let's look at code examples in C++, Java, and Python, showcasing the implementation of the same.
C++ Code:
Output:
Frequency of 2 is: 4
Frequency of 4 is: 3
Frequency of 7 is: 2
Frequency of 8 is: 1
Explanation:
We begin by defining a function, Freq_count, which takes vector/ array and the variable size as inputs.
- Inside the function, a new variable frequency is initialized to the value of 1. And a for loop, along with an if-else statement, is then used to traverse through the array of elements.
- If the current element equals the previous one, it increments the frequency by 1. Otherwise (else), we print the frequency using cout and reinitialize it to 1.
- Next, we declare and intialise an unsorted array with integer elements. We also declare an integer variable, N, which determines the size of the vector or the array.
- We then use the in-built sort() function to sort through the array with array.begin() and array.end() defining the range.
- Both the array and variable N are passed to the function, Freq_count as inputs.
- The function prints the frequency of each element when invoked, and the program closes with zero errors.
Complexity Analysis:
Time Complexity - O(n log n), since it uses only one loop and an inbuilt sorting function.
Space Complexity - O(1)
Java Code:
Python Code:
Count Frequency Of Each Element In An Array With Space Optimization
Space optimization methods aim to minimize the space used to count the frequencies without using additional data structures like hash maps or arrays. The idea is to manipulate the input array itself to store frequency information, thereby reducing the space complexity.
The given space optimization method in C++ takes advantage of the fact that the array is sorted. By modifying the array in place and marking processed elements as 0, it avoids using extra space for storing frequencies. This approach has a time complexity of O(n^2), as it uses two nested loops, but it achieves space optimization by reusing the input array. Let’s understand how to find frequency of each element in an array with the help of the following code and a detailed explanation of the same.
Task Given: Count the frequency of each element in an array given.
Array Given:
array[] = { 2, 4, 2, 7, 8, 4, 7, 2, 2, 4}
C++ Code:
Output:
Frequency of 2 is: 4
Frequency of 4 is: 3
Frequency of 7 is: 2
Frequency of 8 is: 1
Explanation:
In the example above, we include the iostream file and use the namespace std.
- The freqCount function takes two parameters: an integer array, array[] and an integer size, representing the size of the array.
- The freqCount function is responsible for counting the frequency of each element in the array and printing the results.
- The outer loop iterates through each element of the array, starting from the first element (index 0) and going up to the last element (index size-1). Inside the outer loop, there's an if statement to check if the current element is already processed.
- If the element is 0, it means it has been previously processed, so the loop continues to the next iteration. If the current element is not 0, a variable count is initialized to 1. This variable will store the frequency of the current element.
- The inner loop starts from the next element (index i+1) and goes up to the last element (index size-1) of the array. In the inner loop, it checks if the current element is the same as the one selected in the outer loop. If they are the same, it means the element is repeating in the array.
- When a repeating element is found, the count is incremented, and the repeating element is marked as processed by setting its value to 0. This helps avoid counting the same element again in subsequent iterations.
- After the inner loop, the count variable contains the frequency of the current element.
- The program then prints the frequency of the current element using cout.
- The main function initializes an integer array, array[] with values {2, 4, 2, 7, 8, 4, 7, 2, 2, 4}.
- It calculates the size of the array using sizeof(array) / sizeof(array[0]) and passes both the array and its size to the freqCount function.
- The freqCount function processes the array and prints the frequency of each element.
- The program ends by returning 0 from the main function, indicating successful execution.
Complexity Analysis:
Time Complexity - O(n log2n), since O(n log2n) is used for binary search.
Space Complexity - O(1)
Java Code:
Python Code:
Efficiency Comparison Of 4 Methods To Count Frequency Of Each Element In An Array
Here's the comparison of the four methods for counting frequencies of array elements, represented in the form of a table:
Method | Time Complexity | Space Complexity | Efficiency |
---|---|---|---|
Using Two Loops | O(n^2) | O(n) | Least Efficient |
Using Hash Map | O(n) | O(n) | Most Efficient |
By Sorting Array | O(n log n) | O(1) | Efficient |
Space Optimization | O(n^2) | O(1) | Efficient Space Use |
Conclusion
In conclusion, counting the frequency of each element in an array is a fundamental task in data analysis, etc. We can achieve this task using the following four methods (as discussed above).
- The first method uses a nested loop structure where the outer loop helps to iterate over array elements, and the inner loop counts the number of occurrences of each element.
- The second method makes use of a hash map or an unordered map to store the element and frequency as an <int, int> pair. This is the most time-efficient yet simple solution.
- The third method involves sorting the array and then counting the frequency of elements in an array given.
- Lastly, the space-optimized method also uses a similar approach, but in addition to the sorting, it also uses a binary search function that reduces the memory requirement and is the most efficient space-optimized solution.
Also read- 51 C++ Interview Questions For Freshers & Experienced (With Answers)
Frequently Asked Questions
Q. How to find the frequency of a given element in a sorted array?
Say we are given a sorted array and an element whose frequency is to be found out. In this case, we can make use of a linear search function using a single loop to check for the occurrence of the element and use a variable as a counter. Since this is an assorted array, once the control passes over to a greater element, then we know that any other occurrence of the element is not possible. Hence we can break out of the loop and print the result. Let’s understand how to find frequency of each element in an array with the following code example.
Code:
Output:
Frequency of 5 is: 4
Explanation:
- In the main function, a sorted array and a number whose frequency is to be found out is given.
- The integer variable, size, determines the size of the array, which is then passed to the Freq_count function. In this function, a new variable frequency is initialized to the value 0.
- The for loop is used to traverse through the array of elements and increment the frequency by 1 if the current element equals the given element.
- If not then, then we continue to the next element.
- Once the control passes over to a greater element, we break the loop since it is a sorted array. Hence we know there would not be any other occurrence of the given element.
Complexity Analysis:
Time Complexity - O(n), since it uses only one loop for searching.
Space Complexity - O(1)
Q. How to count the frequency of words in a string in C?
To count the frequency of words, we need to use a nested loop structure. We iterate over each character of the given string and compare it with the first character of the word in the collections module. If it matches, then we go on to check the further character comparisons, and accordingly, frequency is incremented. Let us understand this method in detail with the following code and explanation.
Code:
Output:
Enter the String: India is a country, and India is great.
Enter a Word: India
Occurrence = 2
Explanation:
- We first take string input using the gets() function and the word whose frequency is to be printed using the next gets() function into an array of string and word, respectively.
- Then the string and word length are determined and stored in the respective variable count. We then use a nested loop function.
- The outer loop iterates over each character of the given string and compares with the first character of the given word in the inner loop.
- If it matches, then we go on to check the further character comparisons until the whole word matches.
- If the whole word is matched, then the word_count variable is incremented by 1, and i is rested to temp to move on to the next comparisons.
Q. What is array frequency?
Array frequency refers to the occurrence or count of each and every unique element in an array. It provides us with information on how many times each minimum element appears in an array. This frequency can then be used to detect patterns and study data for statistical calculations.
Suppose we are given an array [2, 3, 2, 5, 2, 3, 3, 3],
Therefore the frequency of each element is:
Element 2 appears 3 times.
Element 3 appears 4 times.
Element 5 appears 1 time.
Q. What is an example of a frequency array?
A frequency array is an integer array that stores the count frequency of each element in an array. It helps to count the frequency of elements in an array without repeated iteration over the original array again and again. The index of the frequency array corresponds directly to the element, and the value at that index represents frequency.
Here is an example of a Python code:
Output:
Element 0: 0
Element 1: 4
Element 2: 3
Element 3: 2
Element 4: 2
Explanation:
- We first find the maximum element in the array and then initialize a frequency array of maximum length equal to the maximum element +1.
- As we iterate over each element in a given array, we increase the frequency array value, at an index equal to the current element, by 1.
- Hence The time complexity is reduced to O(n).
By now, you must know how to count frequency of each element in an array in a C++ program. You might also be interested in reading the following:
- References In C++ | Declare, Types, Properties & More (+Examples)
- Storage Classes In C++ & Its Types Explained (With Examples)
- New Operator In C++ | Syntax, Usage, Working & More (With Examples)
- Typedef In C++ | Syntax, Application & How To Use It (With Examples)
- Substring Function substr() In C++ Explained With Examples
Login to continue reading
And access exclusive content, personalized recommendations, and career-boosting opportunities.
Comments
Add comment