In this article, we are given an array that may contain duplicate values. We will print all elements and their frequencies if the duplicates exist. We can do this by using two methods:
- Running two loops
- Using Hashing
- Using the Binary search function
Examples:
Input : arr[] = {10, 20, 20, 10, 10, 20, 5, 20}
Output : 10 3
20 4
5 1
Input : arr[] = {10, 20, 20}
Output : 10 1
20 2
A simple solution is to run two loops. For every item count number of times, it occurs. To avoid duplicate printing, keep track of processed items
Example 1: Below is the implementation of the above approach:
Javascript
<script> // JavaScript program to count frequencies of array items function countFreq(arr, n) { let visited = Array.from({ length: n }, (_, i) => false); // Traverse through array elements and // count frequencies for (let i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true) continue; // Count frequency let count = 1; for (let j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } console.log(arr[i] + " " + count); } } // Driver Code let arr = [10, 20, 20, 10, 10, 20, 5, 20]; let n = arr.length; countFreq(arr, n);</script> |
Output:
10 3
20 4
5 1
Time Complexity: O(n2), where n time for each loop.
Auxiliary Space: O(n), for visited array.
Example 2: An efficient solution is to use hashing:
Javascript
<script> function countFreq(arr, n) { var mp = new Map(); // Traverse through array elements and // count frequencies for (var i = 0; i < n; i++) { if (mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i]) + 1) else mp.set(arr[i], 1) } var keys = []; mp.forEach((value, key) => { keys.push(key); }); keys.sort((a, b) => a - b); // Traverse through map and print frequency keys.forEach((key) => { console.log(key + " " + mp.get(key)); }); } var arr = [10, 20, 20, 10, 10, 20, 5, 20]; var n = arr.length; countFreq(arr, n);</script> |
Output:
5 1
10 3
20 4
Example 3: In the above efficient solution, how to print elements in the same order as they appear in input:
Javascript
<script> function countFreq(arr, n) { var mp = new Map(); // Traverse through array elements and // count frequencies for (var i = 0; i < n; i++) { if (mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i]) + 1) else mp.set(arr[i], 1) } // To print elements according to first // occurrence, traverse array one more time // print frequencies of elements and mark // frequencies as -1 so that same element // is not printed multiple times. for (var i = 0; i < n; i++) { if (mp.get(arr[i]) != -1) { console.log(arr[i] + " " + mp.get(arr[i])); mp.set(arr[i], -1); } } } var arr = [10, 20, 20, 10, 10, 20, 5, 20]; var n = arr.length; countFreq(arr, n);</script> |
Output:
10 3
20 4
5 1
Another Efficient Solution (Space optimization): we can find the frequency of array elements using the Binary search function. First, we will sort the array for binary search. Our frequency of element will be ‘(last occ – first occ)+1’ of an element in an array.
Example:
Javascript
//Function to find frequency of elements in the arrayfunction countFreq(arr, n) { arr.sort((a, b) => a - b); //sort array for binary search let i = 0; while (i < n) { //index of first and last occ of arr[i] const first_index = arr.indexOf(arr[i]); const last_index = arr.lastIndexOf(arr[i]); i = last_index; const fre = last_index - first_index + 1; //finding frequency console.log(arr[i] + " " + fre); //printing frequency i++; }}// Driver codeconst arr = [10, 20, 20, 10, 10, 20, 5, 20];countFreq(arr, arr.length); |
5 1 10 3 20 4
Time Complexity: O(n*log2n), where O(log2n) time for the binary search function.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
