Frequency Counting

Before we start

By the end of this page you will be able to:

• See a frequency map as a tally sheet — built in one pass, queried instantly.
• Explain out loud how to find the top-K frequent elements without sorting the full array.
• Recognise the frequency-counting skeleton in anagram checking, character problems, and majority element detection.

Stop at every Pause & Think box.

Picture this first (no code yet)

The insight: counting is free during a single scan. You never need to "look back" to know how many times something appeared — the map remembers for you.

The actual problem

The core operation is simple:

Given a list of items, build a map from each item to the number of times it appears.

from collections import Counter
freq = Counter([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
# freq = {3:2, 1:2, 4:1, 5:3, 9:1, 2:1, 6:1}

That one line solves a dozen interview problems. The hard part isn't building the map — it's knowing what to do with it after. This chapter covers the most important use-cases.

First, the slow way (so you feel the pain)

Problem: find the most frequent element in [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5].

Naïve approach: for each element, count its occurrences by scanning the whole array.

max_count = 0
result = -1
for x in arr:
    count = arr.count(x)     # O(n) scan for every element
    if count > max_count:
        max_count = count
        result = x

arr.count(x) is O(n). Called n times → O(n²) total. For n=100,000: 10 billion operations.

One-pass frequency count: O(n). Same result, no repeated scanning.

The turning point

The key realisation: counting and querying are separate operations. Do the counting in one pass up front. Then answer any number of queries for free.

1. 7 in freq → O(1). Answer: No.
2. freq[5] → O(1). Answer: 3.
3. max(freq, key=freq.get) → O(k) where k is distinct elements. Or use a heap for top-K.

The frequency map makes all three instant after the single O(n) counting pass.

The one idea to remember

Watch it happen, frame by frame

Problem: find the first non-repeating character in "aabbcde".

Build the frequency map in one pass:

Process 'a': freq={'a':1}
Process 'a': freq={'a':2}
Process 'b': freq={'a':2,'b':1}
Process 'b': freq={'a':2,'b':2}
Process 'c': freq={'a':2,'b':2,'c':1}
Process 'd': freq={'a':2,'b':2,'c':1,'d':1}
Process 'e': freq={'a':2,'b':2,'c':1,'d':1,'e':1}

Second pass — scan left to right, return first with count 1:

's'='a': freq['a']=2 → skip
's'='a': skip
's'='b': freq['b']=2 → skip
's'='b': skip
's'='c': freq['c']=1 → RETURN 'c' ✓

freq = {'l':1, 'e':3, 't':1, 'c':1, 'o':1, 'd':1}
Scan: 'l' → count 1 → RETURN 'l' ✓

Now, the code — line by line

Core pattern — build and query:

from collections import Counter, defaultdict

def firstUniqChar(s):
    freq = Counter(s)              # one-pass count: {'l':1, 'e':3, ...}

    for i, ch in enumerate(s):    # second pass — scan in original order
        if freq[ch] == 1:
            return i               # first index with count exactly 1

    return -1                      # all characters repeat

Top K frequent elements (LC #347):

def topKFrequent(nums, k):
    freq = Counter(nums)           # build frequency map

    # Option 1: sort by frequency — O(n log n)
    return sorted(freq, key=freq.get, reverse=True)[:k]

But we can do better with a bucket sort idea — O(n):

def topKFrequent_linear(nums, k):
    freq = Counter(nums)

    # Bucket: index = frequency, value = list of numbers with that frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, count in freq.items():
        buckets[count].append(num)

    # Collect from highest-frequency bucket downward
    result = []
    for count in range(len(buckets) - 1, 0, -1):
        result.extend(buckets[count])
        if len(result) >= k:
            return result[:k]
    return result

Why O(n): frequencies are bounded by n, so the bucket array has at most n+1 slots — filling it is O(n), reading it top-down is O(n).

Why is building the map O(n)?

Each element is visited exactly once. For each visit, a hash map insert/update takes O(1) amortised. Total: n × O(1) = O(n).

Reading back is O(k) for top-K queries, O(1) for single lookups, O(distinct elements) for iterating all entries.

When should I reach for this? (the trigger list)

Reach for a frequency map when:

• Asked about how many times something appears.
• Asked for the most/least frequent element, or top K frequent.
• Checking if two things are anagrams (same characters, same counts).
• Checking if a string/array is a permutation of another.
• Counting elements to detect majority (appears > n/2 times) before Moore's Voting.
• The brute-force answer involves a nested scan: "for each element, count how many times it appears."

The same trick in five disguises

Disguise 1 — Valid Anagram (LC #242)

Two strings are anagrams if they have the same character frequencies.

def isAnagram(s, t):
    return Counter(s) == Counter(t)
    # Or: Counter(s) - Counter(t) == Counter()  (same thing)

Alternatively, subtract counts and check all reach zero:

def isAnagram(s, t):
    if len(s) != len(t): return False
    freq = Counter(s)
    for ch in t:
        freq[ch] -= 1
        if freq[ch] < 0: return False   # t has more of this char than s
    return True

Disguise 2 — Majority Element (LC #169)

Find element appearing > n/2 times. Either use a frequency map and check, or use Moore's Voting (pattern 1.09) for O(1) space.

def majorityElement(nums):
    freq = Counter(nums)
    return max(freq, key=freq.get)    # works because majority always exists

Disguise 3 — Check if Array is Permutation of 1..N

def isPermutation(nums):
    n = len(nums)
    return Counter(nums) == Counter(range(1, n + 1))
    # Or: set(nums) == set(range(1,n+1)) and len(nums)==n  (if all distinct)

Disguise 4 — Ransom Note (LC #383)

Can you build the note from the magazine? Check if every character's count in the note ≤ its count in the magazine.

def canConstruct(ransomNote, magazine):
    mag = Counter(magazine)
    for ch in ransomNote:
        mag[ch] -= 1
        if mag[ch] < 0:
            return False    # magazine ran out of this character
    return True

Disguise 5 — Find All Anagrams in a String (LC #438)

Sliding window of fixed size k = len(p). Maintain a frequency count of the current window; compare with the target frequency count.

def findAnagrams(s, p):
    target = Counter(p)
    window = Counter(s[:len(p)])
    result = []
    if window == target: result.append(0)

    for i in range(len(p), len(s)):
        window[s[i]] += 1                      # add new character
        old = s[i - len(p)]
        window[old] -= 1
        if window[old] == 0: del window[old]   # remove zeroed-out entry
        if window == target: result.append(i - len(p) + 1)

    return result

import heapq

def topKFrequent_heap(nums, k):
    freq = Counter(nums)
    # heap stores (count, num); min-heap keeps the k largest counts
    return [num for count, num in heapq.nlargest(k, freq.items(), key=lambda x: x[0])]

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll build a frequency map in one O(n) pass. Each element is counted in O(1). Then I query the map — existence checks, maximum, or top-K — in O(1) per query or O(n) total for top-K with bucket sort. The key insight is that counting is free during the scan; you never need to revisit elements."

Check yourself

Practice problems

Next up: Grouping by Key — where the hash map doesn't count, it sorts into bins — and the key is a computed signature, not the element itself.