Frequency Arrays

In the world of programming and problem-solving, there’s one trick that keeps popping up like a cheat code: the frequency array.

Whether you're dealing with numbers or characters, a frequency array helps you count occurrences with lightning speed.

Topic Overview

• Introduction
• Steps to Create Frequency Array
• Time and Space Complexity
• When to Use and When not to Use
• Frequency array for Characters with examples

What is a Frequency Array?

A frequency array is just an array where each index represents a possible value, and the value at that index tells you how many times that value appears.

Example:

Array:

arr = {1, 3, 3, 1, 2, 1};

Frequency array (indexed from 0):

Index → 0  1  2  3  
Value → 0  3  1  2

It means:

• 1 appeared 3 times

• 2 appeared once

• 3 appeared twice

How to Create a Frequency Array

Step 1: Know the Range

Before using a frequency array, you must know the maximum value you’re going to store. For example, if numbers go from 0 to 1000, create:

vector<int> freq(1001, 0);

This create a vector of size 1001 (from index 0 to 1000) with initial value at all index as 0.

Step 2: Count Occurrences

Loop through the array and count:

vector<int> arr = {4, 2, 4, 1, 2};
vector<int> freq(1001, 0); // assuming max value is 1000

for (int num : arr) {
    freq[num]++;
}

Now you can get frequency of 4 in O(1):

cout << "4 appears " << freq[4] << " times\n";

Time and Space Complexity

⏱️ Time and Space Complexity of Frequency Arrays

Note:
Use frequency arrays when k (max possible value) is not too large, otherwise space becomes a bottleneck.

When to Use Frequency Arrays

Use them when:

• You need to count how many times numbers or characters appear.

• The values are within a small, known range.

• You want O(1) access to frequencies.

When not to Use Frequency Arrays

Do not use them when:

• Elements are huge (10^9+).

• Keys are strings or floating points.

• Sparse elements with unknown range.

Frequency Arrays for Characters

Count occurrence of letters in a string:

string s = "banana";
vector<int> freq(26, 0); // for 'a' to 'z'

for (char c : s) {
    freq[c - 'a']++;
}

// freq[0] → count of 'a'
// freq[1] → count of 'b' and so on

It will implicitly convert characters into their corresponding ASCII value for calculation of the index.

Check if two Strings are Anagrams:

Two strings are said to be anagrams if all the letters used in both strings have the same frequency.

bool areAnagrams(string a, string b) {
    if (a.size() != b.size()) return false;

    vector<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;
}

• Initially frequency of all letters is 0.
• Traversing through string 'a' increase the frequency of letters present in 'a'.
• Traversing through string 'b' decrease the frequency of letters present in 'b'.
• At last if frequency of all the letters is still 0, it means all the letters appeared in 'a' and 'b' equal number of times.
• Thus 'a' and 'b' are anagrams.

Final Thoughts

Frequency arrays with vectors are one of the most powerful weapons in your C++ toolbox — especially in competitive programming or interviews where time and space matter.

You’ll use them everywhere:

• Counting elements

• Solving string problems

• Optimizing brute force solutions

• Pattern matching

• Duplicate detection

Start recognizing when a problem involves counting or checking appearances — and you’ll start seeing how frequency arrays can make it faster, cleaner, and easier.

For more amazing content like this
Join our Official Whatsapp Channel by clicking here

Till then

Happy Coding!