← Back to DSA Course | Chapter 7: Hashing | Lesson 5 of 5

Frequency Counting

Frequency counting is like keeping tally marks for how many times each candy color shows up in a jar.

In this page:

  1. What is Frequency Counting
  2. Using a Hash Map
  3. Using an Array
  4. Common Uses
  5. Complexity
Syntax
markup 
freq = {}
for item in collection:
    freq[item] = freq.get(item, 0) + 1

counts = [0] * range_size    # for small integer values
for x in collection:
    counts[x] += 1

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;
}
Related Topics

Counting Sort · Anagram and Frequency Count · Two Sum Problem · Collision Handling

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Reading freq[x] from an unordered_map and assuming it is 0 without inserting, when [] does insert a zero-valued entry.
  2. Using a fixed-size array when values can be negative or large, so the index goes out of range.
  3. Forgetting to reset the counts between test cases.
Chapter Summary
  • Hashing maps keys to values for fast lookup, using hash maps and hash sets.
  • Collision handling deals with different keys that map to the same place.
  • Hashing solves problems like Two Sum and frequency counting.
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Two Sum Problem Next Lesson → Recursion Deep Dive

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.