.png)
Count Frequency of Each Element in an Array
Problem Statement
Given an array of n elements, find the frequency of each element.
- Frequency is the number of times an element appears in the array.
- The array can contain positive, negative, or zero values.
- The goal is to output each unique element and its count.
Example 1
Input:
arr = [1, 2, 2, 3, 1, 4, 2]
Output:
1 -> 2
2 -> 3
3 -> 1
4 -> 1
Explanation:
- 1 appears twice, 2 appears three times, 3 appears once, 4 appears once.
Example 2
Input:
arr = [5, 6, 5, 6, 5]
Output:
5 -> 3
6 -> 2
Why This Problem Is Important
- Tests understanding of arrays, counting, and hashing.
- Foundation for data analytics, frequency analysis, and interview coding questions.
- Prepares you for advanced problems like majority element, mode of an array, and duplicate detection.
Approaches to Solve the Problem
- Using Hash Map / Dictionary (Most Efficient) ✅
- Using Sorting and Counting (Less Extra Space) ✅
- Brute Force (Nested Loops, Not Recommended)
Approach 1: Using Hash Map / Dictionary
Idea
- Traverse the array.
- Maintain a frequency map where key = element, value = count.
- For each element, increase its count in the map.
- Output the map at the end.
Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n)
C++ Implementation
#include
#include
#include
using namespace std;
int main() {
vector arr = {1, 2, 2, 3, 1, 4, 2};
unordered_map freq;
for(int num : arr)
freq[num]++;
cout << "Frequency of each element:\n";
for(auto it : freq)
cout << it.first << " -> " << it.second << endl;
}
Java Implementation
import java.util.*;
public class CountFrequency {
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 1, 4, 2};
HashMap freq = new HashMap<>();
for(int num : arr)
freq.put(num, freq.getOrDefault(num, 0) + 1);
System.out.println("Frequency of each element:");
for(int key : freq.keySet())
System.out.println(key + " -> " + freq.get(key));
}
}
Python Implementation
arr = [1, 2, 2, 3, 1, 4, 2]
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
print("Frequency of each element:")
for key, value in freq.items():
print(f"{key} -> {value}")
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1, 2, 2, 3, 1, 4, 2};
Dictionary freq = new Dictionary();
foreach(int num in arr)
freq[num] = freq.GetValueOrDefault(num,0) + 1;
Console.WriteLine("Frequency of each element:");
foreach(var kvp in freq)
Console.WriteLine(kvp.Key + " -> " + kvp.Value);
}
}
JavaScript Implementation
let arr = [1, 2, 2, 3, 1, 4, 2];
let freq = {};
arr.forEach(num => freq[num] = (freq[num] || 0) + 1);
console.log("Frequency of each element:");
for(let key in freq){
console.log(`${key} -> ${freq[key]}`);
}
Approach 2: Using Sorting
Idea
- Sort the array.
- Traverse the array and count consecutive occurrences.
- Print the element and its count when a new element is encountered.
Time & Space Complexity
- Time Complexity: O(n log n) (due to sorting)
- Space Complexity: O(1) if in-place sorting
Python Implementation (Sorting)
arr = [1, 2, 2, 3, 1, 4, 2]
arr.sort()
n = len(arr)
i = 0
while i < n:
count = 1
while i + 1 < n and arr[i] == arr[i+1]:
count += 1
i += 1
print(f"{arr[i]} -> {count}")
i += 1
Approach 3: Brute Force (Nested Loops)
Idea
- For each element in the array, count how many times it occurs by scanning the entire array.
- Keep track of elements already counted to avoid duplicates in the output.
- Simple but inefficient for large arrays.
Time & Space Complexity
- Time Complexity: O(n²) — nested loops for counting
- Space Complexity: O(1) extra (not counting output storage)
Python Implementation
arr = [1, 2, 2, 3, 1, 4, 2]
counted = []
n = len(arr)
for i in range(n):
if arr[i] not in counted:
freq = 0
for j in range(n):
if arr[i] == arr[j]:
freq += 1
print(f"{arr[i]} -> {freq}")
counted.append(arr[i])
Output:
1 -> 2
2 -> 3
3 -> 1
4 -> 1
C++ Implementation
#include
#include
using namespace std;
int main() {
vector arr = {1, 2, 2, 3, 1, 4, 2};
vector counted;
int n = arr.size();
for(int i = 0; i < n; i++){
bool alreadyCounted = false;
for(int k = 0; k < counted.size(); k++){
if(arr[i] == counted[k]){
alreadyCounted = true;
break;
}
}
if(!alreadyCounted){
int freq = 0;
for(int j = 0; j < n; j++){
if(arr[i] == arr[j])
freq++;
}
cout << arr[i] << " -> " << freq << endl;
counted.push_back(arr[i]);
}
}
}
Java Implementation
import java.util.*;
public class CountFrequencyBruteForce {
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 1, 4, 2};
ArrayList counted = new ArrayList<>();
for(int i = 0; i < arr.length; i++){
if(!counted.contains(arr[i])){
int freq = 0;
for(int j = 0; j < arr.length; j++){
if(arr[i] == arr[j])
freq++;
}
System.out.println(arr[i] + " -> " + freq);
counted.add(arr[i]);
}
}
}
}
C# Implementation
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1, 2, 2, 3, 1, 4, 2};
List counted = new List();
for(int i = 0; i < arr.Length; i++){
if(!counted.Contains(arr[i])){
int freq = 0;
for(int j = 0; j < arr.Length; j++){
if(arr[i] == arr[j])
freq++;
}
Console.WriteLine($"{arr[i]} -> {freq}");
counted.Add(arr[i]);
}
}
}
}
JavaScript Implementation
let arr = [1, 2, 2, 3, 1, 4, 2];
let counted = [];
for(let i = 0; i < arr.length; i++){
if(!counted.includes(arr[i])){
let freq = 0;
for(let j = 0; j < arr.length; j++){
if(arr[i] === arr[j])
freq++;
}
console.log(`${arr[i]} -> ${freq}`);
counted.push(arr[i]);
}
}
Summary of Approaches for Counting Frequency
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Hash Map / Dictionary | O(n) | O(n) | Most efficient, recommended |
| Sorting | O(n log n) | O(1) extra | In-place, but array gets sorted |
| Brute Force (Nested Loops) | O(n²) | O(1) extra | Simple, but slow for large arrays |
Mastering this problem prepares you for majority element, duplicate detection, and analytics tasks.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
