Frequency Table
A frequency table is an application of hash maps that counts the occurrences of each element in a collection.
11 CHARS · 8 DISTINCT
NEW KEY
0
1
2
3
4
5
6
7
8
9
10
Counts
␣
d
e
h
l
o
r
w
'h' seen for the first time — start its count at 1.
Next
'e' seen for the first time — start its count at 1.
Text
Intuition
Imagine you are tallying votes in an election. You read each ballot name and add a tally mark next to that candidate's name on a chalkboard. If the name isn't on the board yet, you write it down with one mark. This chalkboard is your Frequency Table.
Concept
A Frequency Table is typically implemented using a Hash Map where:
- Key: The element (e.g., a character or number).
- Value: The count of how many times that element has appeared so far.
How it Works
Building the Table:
- Initialize an empty Hash Map.
- Iterate through the input array or string.
- For each element:
- If it exists in the map, increment its value (count + 1).
- If it doesn't exist, add it to the map with value 1.
Step-by-Step Breakdown
Watch the visualization:
- Input Processing: The algorithm steps through the string one character at a time.
- Table Update: If the character is new, a new entry appears. If it exists, the count increments.
- Result: The final table shows the distribution of all elements.
When to Use
Applications:
- Finding the most frequent element (Mode).
- Checking if two strings are Anagrams (same character counts).
- Sorting elements by frequency.
- Data compression (Huffman Coding).
When NOT to Use
- Sorted Data: If data is already sorted, you can count frequencies in O(1) space by iterating.
- Small Range: If counting integers in a small range (e.g., 0-100), a simple array is faster than a Hash Map.
How to Identify
"Count occurrences", "Most frequent", "Anagram", "Majority Element".
Applying for software engineering roles? Free, no sign-up: