Last Updated on May 5, 2023 by Prepbytes
For each unique element in the array, we must count its occurrence in this program. Maintaining one array to hold the counts of each array element is one strategy for solving this issue. As you loop through the array, count how often each element appears and then store the results in another array.
arr = {1, 2, 3, 5, 2, 9, 7, 3, 5}In the above example, 1 appeared 1 time, 2 appeared 2 times, 3 appeared 2 times, 5 occurs 2 times, 7 occurs 1 time, and 9 occurs 1 time.
Methods to Find the Frequency of Elements in An Array
There are different methods to find the frequency of elements in an array :
Method 1 To Find the Frequency of Elements in an Array With Extra Space
To find the frequency of elements in an array, we will use two loops and we will count the frequency of each element.
- Step 1: Create an array of size n in order to check the status of the visited items.
- Step 2: From index 0 to index n, loop over the elements and skip the ones where (visited[i]==1).
- Step 3: Make the variable count = 1 to maintain the frequency count.
- Step 4: Continually loop from index i+1 to n.
- Step 5: Determine whether arr[i]==arr[j], then add 1 to the count and set visited[j]=1.
- Step 6: Print the element and the value of the count once the for loop has finished iterating.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1, 2, 3, 5, 2, 9, 7, 3, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int visited[n];
for(int i=0; i<n; i++)
{
if(visited[i]!=1)
{
int count = 1;
for(int j=i+1; j<n; j++)
{
if(arr[i]==arr[j])
{
count++;
visited[j]=1;
}
}
cout<<arr[i]<<" appears "<<count<<" times "<<endl;
}
}
return 0;
} Output
1 appears 1 times
2 appears 2 times
3 appears 2 times
5 appears 2 times
9 appears 1 times
7 appears 1 times Time Complexity : O(n^2)
Space Complexity : O(n)
Method 2 To Find the Frequency of Elements in an Array Without Extra Space
To find the frequency of elements in an array Without Extra Space, we will use the same approach as above but this time we will not use the visited array to count the occurrence of the visited elements in an array.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
void countFrequency(int *arr, int n){
for (int i = 0; i < n; i++){
int flag = 0;
int count = 0;
for (int j = i+1; j < n; j++){
if (arr[i] == arr[j]){
flag = 1;
break;
}
}
if (flag == 1)
continue;
for(int j = 0;j<=i;j++){
if(arr[i]==arr[j])
count +=1;
}
cout << arr[i] << " appears " << count << " times " << endl;
}
}
int main()
{
int arr[] = {1, 2, 3, 5, 2, 9, 7, 3, 5};
int n = sizeof(arr)/sizeof(arr[0]);
countFrequency(arr, n);
return 0;
} Output
1 appears 1 times
2 appears 2 times
3 appears 2 times
5 appears 2 times
9 appears 1 times
7 appears 1 times Time Complexity : O(n^2)
Space Complexity : O(1)
Method 3 To Find the Frequency of Elements in an Array Using HashMap
In this method, the frequency of the elements will be stored using a hash map.
The steps are as follows:
- Step 1: Make a say, mp, unordered_map.
- Step 2: Using a loop, cycle over an array.
- Step 3: Adjust mp[arr[i]]++
- Step 4: Run a loop across the map once you’ve finished iterating.
- Step 5: Key-value pair of hashmap is printed at last.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
// Main function to run the program
int main()
{
int arr[] = {1, 2, 3, 5, 2, 9, 7, 3, 5};
int n = sizeof(arr)/sizeof(arr[0]);
unordered_map <int, int>mp;
for(int i=0; i<n; i++)
{
mp[arr[i]]++;
}
for(auto it:mp)
{
cout<<it.first<<" appears "<<it.second<<" times" << endl;
}
} Output
1 appears 1 times
2 appears 2 times
3 appears 2 times
5 appears 2 times
9 appears 1 times
7 appears 1 times Conclusion
In this article, we have discussed how to find the frequency of elements in an array with different approaches i.e. with the extra space, without extra space and also with hashmap. It is considered one of the most famous interview questions and can be asked in different approaches.
Frequently Asked Questions to Find the Frequency of Elements in an Array
Q1. What is a frequency array?
Ans. A frequency array, also known as a frequency distribution, is an array of frequencies organised according to variable values. The multiple frequency distributions that make up the distinct rows and columns of a bivariate frequency are sometimes referred to as a "array".
Q2. Which data structure is used to identify the member in an array that is utilised the least frequently?
Ans. Applying hashing is a practical remedy. In this approach, elements are created, stored, and their frequency counts are represented as key-value pairs in a hash table. Then, after navigating the hash table, we print the key with the lowest value.
Q3. Which algorithm works best to find a specific element in an array?
Ans. The best method for locating a value in an unsorted array is sequential search. 1 However, we can perform much better if the array is sorted in increasing order by value. We apply a technique known as binary search.
Q4. Which sorting and arraying technique is the most effective?
Ans. One of the most popular sorting algorithms is quicksort since it is also one of the most effective. The first step is to choose a pivot number. This number will divide the data, with smaller numbers on its left and larger numbers on its right.
Q5. Is it simple to delete a component from an array?
Ans. You can use the pop() function to remove the final element from an array or the shift() method to remove the first element if you want to remove anything from an array.