Learn Frequency Counting — Free DSA Tutorial

What is Frequency Counting

Frequency counting means tallying how many times each distinct value shows up in a collection, which is the building block behind detecting duplicates, anagrams, and mode statistics. It shows up constantly as a preprocessing step before a harder algorithm runs.

Example: What is Frequency Counting

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int arr[] = {1, 2, 2, 3, 1, 1};
	unordered_map<int, int> freq;
	for (int x : arr) freq[x]++;
	for (auto& p : freq) cout << p.first << ": " << p.second << endl;
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 2, 2, 3, 1, 1};
		HashMap<Integer, Integer> freq = new HashMap<>();
		for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
		for (int key : freq.keySet()) System.out.println(key + ": " + freq.get(key));
	}
}

arr = [1, 2, 2, 3, 1, 1]
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1
for k, v in freq.items():
    print(k, ":", v)

#include <stdio.h>
int main() {
	int arr[] = {1, 2, 2, 3, 1, 1};
	int freq[10] = {0};
	for (int i = 0; i < 6; i++) freq[arr[i]]++;
	for (int i = 0; i < 10; i++) if (freq[i] > 0) printf("%d: %d\n", i, freq[i]);
	return 0;
}

Using a Hash Map

A hash map is the general-purpose tool for this: each distinct value becomes a key, and its count is the value, updated by incrementing on every occurrence. This works for any kind of data, including strings and large or sparse number ranges.

Example: Using a Hash Map

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
	string word = "banana";
	unordered_map<char, int> freq;
	for (char c : word) freq[c]++;
	cout << "a appears " << freq['a'] << " times";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		String word = "banana";
		HashMap<Character, Integer> freq = new HashMap<>();
		for (char c : word.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
		System.out.println("a appears " + freq.get('a') + " times");
	}
}

word = "banana"
freq = {}
for c in word:
    freq[c] = freq.get(c, 0) + 1
print("a appears", freq['a'], "times")

#include <stdio.h>
int main() {
	char word[] = "banana";
	int freq[256] = {0};
	for (int i = 0; word[i]; i++) freq[(int)word[i]]++;
	printf("a appears %d times", freq['a']);
	return 0;
}

Using an Array

When values are small non-negative integers (like ASCII character codes or array indices within a known range), a plain array indexed by the value itself is faster and avoids hashing overhead entirely. It's the same idea as a hash map but with the key baked directly into the array position.

Example: Using an Array

#include <iostream>
#include <string>
using namespace std;
int main() {
	string word = "hello";
	int freq[26] = {0};
	for (char c : word) freq[c - 'a']++;
	cout << "l appears " << freq['l' - 'a'] << " times";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String word = "hello";
		int[] freq = new int[26];
		for (char c : word.toCharArray()) freq[c - 'a']++;
		System.out.println("l appears " + freq['l' - 'a'] + " times");
	}
}

word = "hello"
freq = [0] * 26
for c in word:
    freq[ord(c) - ord('a')] += 1
print("l appears", freq[ord('l') - ord('a')], "times")

#include <stdio.h>
int main() {
	char word[] = "hello";
	int freq[26] = {0};
	for (int i = 0; word[i]; i++) freq[word[i] - 'a']++;
	printf("l appears %d times", freq['l' - 'a']);
	return 0;
}

Common Uses

This pattern underlies checking whether two strings are anagrams (compare their frequency tables), finding the most frequent element, and detecting duplicates without sorting. Recognizing 'I need to know how often things occur' is often the first step toward spotting this pattern in a problem.

Example: Common Uses

#include <iostream>
#include <string>
using namespace std;
bool isAnagram(string a, string b) {
	int freq[26] = {0};
	for (char c : a) freq[c - 'a']++;
	for (char c : b) freq[c - 'a']--;
	for (int f : freq) if (f != 0) return false;
	return true;
}
int main() {
	cout << (isAnagram("listen", "silent") ? "Anagram" : "Not anagram");
	return 0;
}

public class Main {
	static boolean isAnagram(String a, String b) {
		int[] freq = new int[26];
		for (char c : a.toCharArray()) freq[c - 'a']++;
		for (char c : b.toCharArray()) freq[c - 'a']--;
		for (int f : freq) if (f != 0) return false;
		return true;
	}
	public static void main(String[] args) {
		System.out.println(isAnagram("listen", "silent") ? "Anagram" : "Not anagram");
	}
}

def is_anagram(a, b):
    freq = [0] * 26
    for c in a:
        freq[ord(c) - ord('a')] += 1
    for c in b:
        freq[ord(c) - ord('a')] -= 1
    return all(f == 0 for f in freq)

print("Anagram" if is_anagram("listen", "silent") else "Not anagram")

#include <stdio.h>
int isAnagram(char *a, char *b) {
	int freq[26] = {0};
	for (int i = 0; a[i]; i++) freq[a[i] - 'a']++;
	for (int i = 0; b[i]; i++) freq[b[i] - 'a']--;
	for (int i = 0; i < 26; i++) if (freq[i] != 0) return 0;
	return 1;
}
int main() {
	printf(isAnagram("listen", "silent") ? "Anagram" : "Not anagram");
	return 0;
}

Complexity

Building the frequency table takes O(n) time to scan the input once. The extra space is O(k), where k is the number of distinct values you're tracking, which can be much smaller than n if values repeat heavily.

Example: Complexity

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int arr[] = {4, 4, 4, 2, 2, 9};
	int n = 6;
	unordered_map<int, int> freq;
	for (int i = 0; i < n; i++) freq[arr[i]]++;
	cout << "Scanned " << n << " items, " << freq.size() << " distinct keys";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 4, 4, 2, 2, 9};
		HashMap<Integer, Integer> freq = new HashMap<>();
		for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
		System.out.println("Scanned " + arr.length + " items, " + freq.size() + " distinct keys");
	}
}

arr = [4, 4, 4, 2, 2, 9]
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1
print("Scanned", len(arr), "items,", len(freq), "distinct keys")

#include <stdio.h>
int main() {
	int arr[] = {4, 4, 4, 2, 2, 9};
	int n = 6;
	int freq[10] = {0};
	int distinct = 0;
	for (int i = 0; i < n; i++) {
		if (freq[arr[i]] == 0) distinct++;
		freq[arr[i]]++;
	}
	printf("Scanned %d items, %d distinct keys", n, distinct);
	return 0;
}

Frequency Counting

What is Frequency Counting

Using a Hash Map

Using an Array

Common Uses

Complexity

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code