Counting frequencies of array elements
Last Updated : 01 Jul, 2025
Given an array arr[] of non-negative integers which may contain duplicate elements. Return the frequency of each distinct element present in the array.
Examples:
Input : arr[] = [10, 20, 10, 5, 20]
Output : [[10, 2], [20, 2], [ 5, 1]]
Explanation: Here, 10 occurs 2 times, 20 occurs 2 times, and 5 occurs once.
Input : arr[] = [10, 20, 20]
Output : [[10, 1], [20, 2]]
Explanation: Here, 10 occurs 1 time, 20 occurs 2 times.
[Naive Approach] Brute Force O(n^2) Time O(n) Space
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.
C++ #include <iostream> #include <vector> using namespace std; vector<vector<int>> countFreq(vector<int>& arr){ int n = arr.size(); // Mark all array elements as not visited vector<bool> visited(n , false); vector<vector<int>>ans; for (int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i] == true) continue; // store the frequency int count = 1; for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } ans.push_back({arr[i] , count}); } return ans; } int main(){ vector <int> arr = {10, 20, 10, 5, 20}; vector<vector<int>>ans = countFreq(arr); for (auto x : ans){ cout << x[0] << ' '<< x[1] <<'\n'; } return 0; } import java.util.ArrayList; public class GFG { public static ArrayList<ArrayList<Integer>> countFreq(int[] arr) { int n = arr.length; // Mark all array elements as not visited boolean[] visited = new boolean[n]; ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); for (int i = 0; i < n; i++) { // Skip this element if already processed if (visited[i]) continue; int count = 1; // store the frequency for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { visited[j] = true; count++; } } ArrayList<Integer> temp = new ArrayList<>(); temp.add(arr[i]); temp.add(count); ans.add(temp); } return ans; } public static void main(String[] args) { int[] arr = {10, 20, 10, 5, 20}; ArrayList<ArrayList<Integer>> ans = countFreq(arr); for (ArrayList<Integer> x : ans) { System.out.println(x.get(0) + " " + x.get(1)); } } } def countFreq(arr): n = len(arr) # Mark all array elements as not visited visited = [False] * n ans = [] for i in range(n): # Skip this element if already processed if visited[i]: continue #store the frequency count = 1 for j in range(i + 1, n): if arr[i] == arr[j]: visited[j] = True count += 1 ans.append([arr[i], count]) return ans if __name__ == '__main__': arr = [10, 20, 10, 5, 20] ans = countFreq(arr) for x in ans: print(x[0], x[1])
using System; using System.Collections.Generic; class GFG { public static List<List<int>> countFreq(int[] arr){ int n = arr.Length; // Mark all array elements as not visited bool[] visited = new bool[n]; List<List<int>> ans = new List<List<int>>(); // Skip this element if already processed for (int i = 0; i < n; i++){ if (visited[i]) continue; // store the frequency int count = 1; for (int j = i + 1; j < n; j++){ if (arr[i] == arr[j]){ visited[j] = true; count++; } } List<int> temp = new List<int>(); temp.Add(arr[i]); temp.Add(count); ans.Add(temp); } return ans; } static void Main(){ int[] arr = {10, 20, 10, 5, 20}; List<List<int>> ans = countFreq(arr); foreach (var x in ans){ Console.WriteLine(x[0] + " " + x[1]); } } } function countFreq(arr) { let n = arr.length; // Mark all array elements as not visited let visited = Array(n).fill(false); let ans = []; // Skip this element if already processed for (let i = 0; i < n; i++) { if (visited[i]) continue; // store the frequency let count = 1; for (let j = i + 1; j < n; j++) { if (arr[i] === arr[j]) { visited[j] = true; count++; } } ans.push([arr[i], count]); } return ans; } // Driver Code let arr = [10, 20, 10, 5, 20]; let ans = countFreq(arr); for (let x of ans) { console.log(x[0], x[1]); } [Efficient Solution] using hashing - O(n) Time and O(n) Space
An efficient solution is using a hash map (e.g. unordered_map in C++, HashMap in Java, dict in Python, or Dictionary in C#), we can store elements as keys and their frequencies as values.
C++ #include <iostream> #include <unordered_map> #include <vector> using namespace std; vector<vector<int>> countFreq(vector<int>& arr){ unordered_map<int, int> mp; vector<vector<int>> ans; // Count frequency using unordered_map and //build ans in order of first appearance for (int num : arr){ if (mp.find(num) == mp.end()){ mp[num] = 1; ans.push_back({num, 1}); } else{ mp[num]++; // Update frequency in ans list for (auto &x : ans){ if (x[0] == num){ x[1]++; break; } } } } return ans; } int main(){ vector<int> arr = {10, 20, 10, 5, 20}; vector<vector<int>> ans = countFreq(arr); for (auto x : ans){ cout << x[0] << " " << x[1] << endl; } return 0; } import java.util.HashMap; import java.util.ArrayList; public class GFG { public static ArrayList<ArrayList<Integer>> countFreq(int[] arr) { HashMap<Integer, Integer> mp = new HashMap<>(); ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); // Count frequency using HashMap and // build ans in order of first appearance for (int num : arr) { if (!mp.containsKey(num)) { mp.put(num, 1); ArrayList<Integer> temp = new ArrayList<>(); temp.add(num); temp.add(1); ans.add(temp); } else { mp.put(num, mp.get(num) + 1); // Update frequency in ans list for (ArrayList<Integer> x : ans) { if (x.get(0).equals(num)) { x.set(1, x.get(1) + 1); break; } } } } return ans; } public static void main(String[] args) { int[] arr = {10, 20, 10, 5, 20}; ArrayList<ArrayList<Integer>> ans = countFreq(arr); for (ArrayList<Integer> x : ans) { System.out.println(x.get(0) + " " + x.get(1)); } } } def countFreq(arr): mp = {} ans = [] for num in arr: if num not in mp: # Count frequency using HashMap and # build ans in order of first appearance mp[num] = 1 ans.append([num, 1]) else: mp[num] += 1 # update count in ans list for x in ans: if x[0] == num: x[1] += 1 break return ans if __name__ == "__main__": arr = [10, 20, 10, 5, 20] ans = countFreq(arr) for x in ans: print(x[0], x[1]) using System; using System.Collections.Generic; class GFG { public static List<List<int>> countFreq(int[] arr){ Dictionary<int, int> mp = new Dictionary<int, int>(); List<List<int>> ans = new List<List<int>>(); // Count frequency using HashMap and // build ans in order of first appearance foreach (int num in arr){ if (!mp.ContainsKey(num)){ mp[num] = 1; List<int> temp = new List<int> { num, 1 }; ans.Add(temp); } else{ mp[num]++; // / Update frequency in ans list foreach (var x in ans){ if (x[0] == num){ x[1]++; break; } } } } return ans; } static void Main(){ int[] arr = {10, 20, 10, 5, 20}; List<List<int>> ans = countFreq(arr); foreach (var x in ans){ Console.WriteLine(x[0] + " " + x[1]); } } } function countFreq(arr) { const mp = {}; const ans = []; const seen = new Set(); // Count frequency using HashMap and // build ans in order of first appearance for (let num of arr) { if (!mp[num]) { mp[num] = 1; seen.add(num); } else { mp[num]++; } } // Update frequency in ans list for (let num of seen) { ans.push([parseInt(num), mp[num]]); } return ans; } // Driver Code const arr = [10, 20, 10, 5, 20]; const ans = countFreq(arr); for (let x of ans) { console.log(x[0] + " " + x[1]); } [Alternate Approach] using binary search (Space optimization)
we can find frequency of array elements using Binary search function . First we will sort the array for binary search . Our frequency of element will be '(last occ - first occ)+1' of a element in a array .
C++ #include <algorithm> #include <iostream> #include <vector> using namespace std; vector<vector<int>> countFreq(vector<int> &arr){ int n = arr.size(); // Sort array for binary search sort(arr.begin(), arr.end()); vector<vector<int>> ans; for (int i = 0; i < n; i++) { // Find first and last occurrence of arr[i] // using lower and upper bound auto firstIter = lower_bound(arr.begin(), arr.end(), arr[i]); auto lastIter = upper_bound(arr.begin(), arr.end(), arr[i]); int firstIndex = firstIter - arr.begin(); int lastIndex = lastIter - arr.begin() - 1; // Calculate frequency int fre = lastIndex - firstIndex + 1; ans.push_back({arr[i], fre}); // Skip counted elements i = lastIndex; } return ans; } int main(){ vector<int> arr = {10 ,20 ,10 ,5 , 20}; vector<vector<int>> ans = countFreq(arr); for (auto x : ans){ cout << x[0] << " " << x[1] << endl; } return 0; } import java.util.ArrayList; import java.util.Arrays; public class GFG { public static ArrayList<ArrayList<Integer>> countFreq(int[] arr) { Arrays.sort(arr); ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); int n = arr.length; int i = 0; while (i < n) { int current = arr[i]; int firstIndex = i; int lastIndex = i; // Find lastIndex by moving forward while (lastIndex + 1 < n && arr[lastIndex + 1] == current) lastIndex++; // Calculate frequency int fre = lastIndex - firstIndex + 1; // Store in ans as ArrayList ArrayList<Integer> temp = new ArrayList<>(); temp.add(current); temp.add(fre); ans.add(temp); // Skip counted elements i = lastIndex + 1; } return ans; } public static void main(String[] args) { int[] arr = {10, 20, 5, 10, 20}; ArrayList<ArrayList<Integer>> ans = countFreq(arr); for (ArrayList<Integer> x : ans) { System.out.println(x.get(0) + " " + x.get(1)); } } } from bisect import bisect_left, bisect_right def countFreq(arr): n = len(arr) # Sort array for binary search arr.sort() ans = [] i = 0 while i < n: # Find first and last occurrence of arr[i] # using bisect_left and bisect_right firstIndex = bisect_left(arr, arr[i]) lastIndex = bisect_right(arr, arr[i]) - 1 # Calculate frequency fre = lastIndex - firstIndex + 1 ans.append([arr[i], fre]) # Skip counted elements i = lastIndex + 1 return ans if __name__ == "__main__": arr = [10, 20, 10, 5, 20] ans = countFreq(arr) for x in ans: print(x[0], x[1])
using System; using System.Collections.Generic; class GFG{ public static List<List<int>> countFreq(int[] arr){ Array.Sort(arr); int n = arr.Length; List<List<int>> ans = new List<List<int>>(); int i = 0; while (i < n){ int current = arr[i]; int firstIndex = i; int lastIndex = i; // Find lastIndex by moving forward while (lastIndex + 1 < n && arr[lastIndex + 1] == current) lastIndex++; // Calculate frequency int fre = lastIndex - firstIndex + 1; // store in arrayList List<int> temp = new List<int> { current, fre }; ans.Add(temp); // Skip counted elements i = lastIndex + 1; } return ans; } static void Main(){ int[] arr = {10, 20, 10, 5, 20}; List<List<int>> ans = countFreq(arr); foreach (var x in ans){ Console.WriteLine(x[0] + " " + x[1]); } } } function countFreq(arr) { arr.sort((a, b) => a - b); const n = arr.length; const ans = []; let i = 0; while (i < n) { let current = arr[i]; let firstIndex = i; let lastIndex = i; // Find lastIndex by moving forward while (lastIndex + 1 < n && arr[lastIndex + 1] === current) lastIndex++; // Calculate frequency const fre = lastIndex - firstIndex + 1; //store in array list ans.push([current, fre]); // Skip counted elements i = lastIndex + 1; } return ans; } // Driver Code const arr = [10, 20, 10, 5, 20]; const ans = countFreq(arr); for (let x of ans) { console.log(x[0], x[1]); } Time Complexity: O(n*log2n) , where O(log2n) time for binary search function .
Auxiliary Space: O(1)
Similar Reads
JavaScript - Counting Frequencies of Array Elements Here are the various approaches to count the frequencies of array elements in JavaScript.Using an Object (Simple and Efficient)This is the most common approach for counting frequency in an array. Each array element becomes a key in the object, and its value is incremented as the element appears.Java
2 min read
Frequency of an element in an array Given an array, a[], and an element x, find a number of occurrences of x in a[].Examples: Input : a[] = {0, 5, 5, 5, 4} x = 5Output : 3Input : a[] = {1, 2, 3} x = 4Output : 0Unsorted ArrayThe idea is simple, we initialize count as 0. We traverse the array in a linear fashion. For every element that
9 min read
Count Distinct ( Unique ) elements in an array Given an array arr[] of length N, The task is to count all distinct elements in arr[]. Examples: Input: arr[] = {10, 20, 20, 10, 30, 10}Output: 3Explanation: There are three distinct elements 10, 20, and 30. Input: arr[] = {10, 20, 20, 10, 20}Output: 2 Naïve Approach: Create a count variable and ru
15 min read
Count Subsequences with ordered integers in Array Given an array nums[] of N positive integers, the task is to find the number of subsequences that can be created from the array where each subsequence contains all integers from 1 to its size in any order. If two subsequences have different chosen indices, then they are considered different. Example
7 min read
Count of smaller or equal elements in sorted array Given a sorted array of size n. Find a number of elements that are less than or equal to a given element. Examples: Input : arr[] = {1, 2, 4, 5, 8, 10} key = 9 Output : 5 Elements less than or equal to 9 are 1, 2, 4, 5, 8 therefore result will be 5. Input : arr[] = {1, 2, 2, 2, 5, 7, 9} key = 2 Outp
15+ min read
Count pairs formed by distinct element sub-arrays Given an array, count number of pairs that can be formed from all possible contiguous sub-arrays containing distinct numbers. The array contains positive numbers between 0 to n-1 where n is the size of the array. Examples: Input: [1, 4, 2, 4, 3, 2] Output: 8 The subarrays with distinct elements are
7 min read