Counting Problems

One of the most powerful uses of a Hash Map is to count the frequency of elements. Whether you are finding the most popular product, detecting anagrams, or analyzing DNA sequences, this pattern is your best friend.

The Core Idea

Iterate through your data and build a map where:

  • Key: The element (character, number, string).
  • Value: The count (frequency).
counts = {}
for item in items:
  counts[item] = counts.get(item, 0) + 1

Interactive Anagram Checker

An Anagram is a word formed by rearranging the letters of another (e.g., “listen” and “silent”). How do we check if two strings are anagrams? By comparing their character frequency maps!

Anagram Visualizer

Map 1
Map 2

Problem 1: Group Anagrams (LeetCode 49)

Given an array of strings, group the anagrams together. Input: ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

The Strategy

We need a Key that represents the anagram group. All anagrams must map to this same key.

  1. Sorted String Key: Sort “eat” → “aet”. Sort “tea” → “aet”.
  2. Count Tuple Key: Count chars (1, 0, 0, ..., 1) (1 ‘a’, 0 ‘b’…).

The sorted string approach is easier to code: O(N * K log K), where K is max string length. The count tuple approach is O(N * K).

def groupAnagrams(strs):
  groups = {}  # Map: Sorted String -> List of original strings

  for s in strs:
    # Sort the string to form the key
    key = tuple(sorted(s))

    if key not in groups:
      groups[key] = []
    groups[key].append(s)

  return list(groups.values())

Problem 2: Top K Frequent Elements (LeetCode 347)

Given an integer array nums and an integer k, return the k most frequent elements.

The Strategy

  1. Count Frequencies: Use a Hash Map.
  2. Sort by Frequency: Use a Heap or Bucket Sort.

Bucket Sort Approach (O(N)): Since frequency cannot exceed N, we can make an array of lists where index i stores numbers that appear i times.

def topKFrequent(nums, k):
  count = {}
  freq = [[] for i in range(len(nums) + 1)]

  # 1. Count frequencies
  for n in nums:
    count[n] = 1 + count.get(n, 0)

  # 2. Fill buckets
  for n, c in count.items():
    freq[c].append(n)

  # 3. Gather top k
  res = []
  for i in range(len(freq) - 1, 0, -1):
    for n in freq[i]:
      res.append(n)
      if len(res) == k:
        return res

Deep Dive Strategy Lab: Counting Problems

Intuition Through Analogy

Think of this chapter like library card catalog lookup. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?