Jayaprasanna Roddam

Posted on Jan 9

Hash Map Frequency Counting

#programming #datastructures #tutorial #beginners

OVERVIEW

Hash Map Frequency Counting is a fundamental technique used to count occurrences
of elements while iterating through data.

Instead of repeatedly scanning the data, we store frequencies in a hash map
(dictionary) and update them in O(1) time per element.

This pattern is widely used in array, string, and prefix-sum based problems.

WHEN TO USE

Use this technique when:

You need counts of elements or characters
You are checking duplicates or uniqueness
You need fast lookups
The order of elements is not the primary concern

TIME & SPACE

Time Complexity : O(N)
Space Complexity : O(N)

CORE IDEA

Traverse the data once
Store element → frequency mapping
Update count as elements appear or disappear

Typical operations:

Increment frequency
Decrement frequency
Check presence or count

EXAMPLE 1: Count Frequency of Elements in an Array

def frequency_count(arr):
freq = {}

for element in arr:
    if element in freq:
        freq[element] += 1
    else:
        freq[element] = 1

return freq

EXAMPLE 2: Character Frequency in a String

def char_frequency(s):
freq = {}

for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

return freq

EXAMPLE 3: Find First Non-Repeating Character

Problem:
Return the first character in a string that appears exactly once.

def first_non_repeating_char(s):
freq = {}

for ch in s:
    freq[ch] = freq.get(ch, 0) + 1

for ch in s:
    if freq[ch] == 1:
        return ch

return None

EXAMPLE 4: Subarray Sum Equals K (Using Prefix Sum + Hash Map)

Problem:
Count number of subarrays whose sum equals k.

Logic:

Use prefix sum
Store frequency of each prefix sum

def subarray_sum_equals_k(nums, k):
prefix_sum = 0
freq = {0: 1}
count = 0

for num in nums:
    prefix_sum += num

    if prefix_sum - k in freq:
        count += freq[prefix_sum - k]

    freq[prefix_sum] = freq.get(prefix_sum, 0) + 1

return count

EXAMPLE 5: Longest Substring with At Most K Distinct Characters

Problem:
Return length of longest substring containing at most k distinct characters.

def longest_substring_k_distinct(s, k):
left = 0
freq = {}
max_len = 0

for right in range(len(s)):

    freq[s[right]] = freq.get(s[right], 0) + 1

while len(freq) &gt; k:
    freq[s[left]] -= 1
    if freq[s[left]] == 0:
        del freq[s[left]]
    left += 1

max_len = max(max_len, right - left + 1)



    

    




return max_len

IDENTIFICATION CHECKLIST

Ask these questions:

Do I need to count occurrences?
Do I need fast existence checks?
Is repeated scanning too slow?
Can frequency changes track window validity?

If yes, Hash Map Frequency Counting is the right approach.

COMMON PITFALLS

Forgetting to delete zero-frequency keys
Using lists instead of hash maps for large ranges
Not initializing base cases (like prefix sum 0)
Overusing space when simple counters suffice

SUMMARY

Store element → count mapping
Enables O(1) updates and lookups
Essential for sliding window and prefix sum patterns
One of the most powerful everyday tools in problem solving

DEV Community