Frequency Arrays
Scenario
You need to count character frequencies for ASCII text, but using a generic Hash Map creates thousands of wrapper objects and incurs hash-computation overhead.
How can you count frequencies using zero hashing math and ensuring perfect cache locality?
Why it exists
Problem: Generic Hash Maps are powerful but memory-heavy. For small, contiguous keysets (like the 26 English letters or 256 ASCII characters), Hash Maps are massive overkill.
Naive approach: Use a standard Hash Map to map characters to integers, paying the penalty of object instantiation and dynamic resizing.
Better idea: Allocate a fixed-size integer array (e.g., size 26) and use direct addressing: subtract the ASCII value of 'a' from the character to get a perfect, collision-free index.
Mental model
Imagine a physical row of 26 mailboxes. You don't need a complex filing system (Hash Map) to find mailbox 'C'; you inherently know it's the 3rd one from the left. You just drop the letter right into it.
A frequency array is a direct-address table. Because characters have underlying integer representations (ASCII/Unicode), you can map them directly to array indices via simple subtraction, achieving O(1) lookups with zero collisions.
Repeated decision: Have we seen this character before? Compute its array index offset, then increment the count at that index.
Explanation
To build a frequency array for lowercase letters, we initialize an array of size 26 with zeros.
When we process the character 'c', we compute its index relative to 'a'. In ASCII, 'a' is 97 and 'c' is 99. `99 - 97 = 2`. We immediately increment `array[2]`.
This completely bypasses hashing. There are no hash functions, no collision handling, and no dynamic resizing. The array stays exactly size 26 regardless of whether the string is 5 characters or 5 billion characters.
Furthermore, an array of 26 integers requires only 104 bytes of memory, fitting perfectly into a modern CPU's L1 cache line. This guarantees zero latency during processing, making it orders of magnitude faster than a Hash Map in low-level languages.
Key points
- O(N) Time: We process the string in a single linear pass.
- O(1) Space: The array is fixed at size 26 or 256. It never grows.
- Cache Locality: Contiguous arrays are prefetched by the CPU, making this vastly faster than navigating the scattered memory of a Hash Map.
Pattern: Direct Addressing / Frequency Array
Recognition cues:
- The problem strictly limits the input to 'lowercase English letters'.
- You are optimizing for extreme performance and memory limits in C++ or Java.
Failure signals
- You are using a Hash Map when the problem states 'contains only lowercase English letters'.
- You are writing a giant switch statement with 26 cases to count characters.
Engineering examples
Data Compression
Building a Huffman Tree requires knowing the exact byte frequencies of a 100GB file.
A 256-element frequency array tracks the exact count of every possible byte with zero memory overhead, running at maximum disk I/O speed.
Cryptography
Breaking a substitution cipher requires analyzing the distribution of letters.
Frequency arrays map the encrypted text into a histogram that can be matched against standard English letter distributions.
When not to use
- Processing arbitrary Unicode strings: Unicode has over 1 million characters. Allocating an array of 1 million integers for a string that only contains 5 distinct characters is a massive waste of memory. Use a Hash Map for sparse distributions.
Common mistakes
- Forgetting the offset subtraction: If you try to execute `array[char]`, high-level languages will throw a type error because the index must be an integer. You must use ASCII values: `int index = char - 'a';`.
- Assuming all alphabets are 26 characters: If the problem allows uppercase and lowercase, the offset math gets complicated. It's often safer to allocate an array of size 128 (standard ASCII) and just use the raw ASCII value `array[char]` without subtracting 'a'.
Glossary
- L1 cache line
- A very small, ultra-fast memory storage unit directly inside the computer processor.
- direct-address table
- An array where each possible key corresponds to exactly one specific index slot.
- dynamic resizing
- Automatically growing or shrinking a data structure when it gets too full or empty.
Recall questions
- Why is a frequency array faster than a Hash Map for counting English letters?
- How do you calculate the array index for a lowercase character 'x'?
- Why shouldn't you use a frequency array for full Unicode text?
Questions & answers
Given two strings restricted to lowercase letters, determine if they are anagrams.
Initialize an array of size 26. Iterate through both strings simultaneously: increment the array for string A's character, and decrement for string B's character. If the array is all zeros at the end, they are anagrams.
Approach: Frequency array direct addressing.
Find the first non-repeating character in a string.
Do a first pass building a frequency array. Do a second pass over the string checking the frequency array. Return the first character with a count of 1.
Approach: Frequency array with 2 passes.
Interesting facts
- Counting Sort algorithm uses this exact logic: it creates a frequency array of the elements, and then rebuilds the sorted array directly from the counts in O(N) time.
Continue learning
Previous: String Traversal
Next: Anagrams
Related: String Traversal
Related: Frequency Counting