Counting and grouping with hashing

Counting is the most common use of a map

A frequency map stores each distinct item with the number of times it appears. One pass builds it: O(n) time and O(d) space, where d is the number of distinct items. Python gives you three ways to write it.

words = ["upi", "card", "upi", "cash", "upi", "card"]

counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts)              # Output: {'upi': 3, 'card': 2, 'cash': 1}

from collections import defaultdict, Counter
dd = defaultdict(int)      # a missing key starts at int(), which is 0
for w in words:
    dd[w] += 1

c = Counter(words)
print(c.most_common(2))    # Output: [('upi', 3), ('card', 2)]
print(c["wallet"])         # Output: 0  (a missing key counts as 0)

Counter is a dict made for counting. Reading a missing key gives 0 instead of a KeyError, and most_common(k) returns the k most common items; items with equal counts come in the order they were first seen.

First unique character

To find the first character that appears exactly once, count everything in a first pass, then walk the string again and return the first index whose count is 1. Two passes are still O(n). The map holds one entry per distinct character, so for lowercase English letters it never has more than 26 entries: O(1) extra space in that case.

Grouping: same key, same list

Grouping puts items that share some property into one list. Choose a key function so that items in the same group get the same key, then keep a dict from key to list. For anagrams ("eat", "tea", "ate") two keys work well:

• The sorted word: "".join(sorted(w)) turns all three into "aet". Cost O(m log m) for a word of length m.
• A count tuple: 26 counts, one per letter, stored as a tuple because a list cannot be a key. Cost O(m) per word, better for long words.

from collections import defaultdict

groups = defaultdict(list)
for w in ["eat", "tea", "tan", "ate", "nat", "bat"]:
    groups["".join(sorted(w))].append(w)
print(list(groups.values()))
# Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Top-k frequent, with a tie rule

"Return the k most frequent words" needs a rule for ties, or two correct programs can print different answers. A common rule: higher count first, and for equal counts, alphabetical order. Sorting by the key (−count, word) does both at once. Always ask about ties in an interview.

from collections import Counter

def top_k(words, k):
    counts = Counter(words)
    ranked = sorted(counts, key=lambda w: (-counts[w], w))
    return ranked[:k]

print(top_k(["b", "a", "c", "a", "b", "d"], 2))   # Output: ['a', 'b']

A heap can do this in O(d log k) (Module 8), and grouping words into buckets by count can do it in O(n). The sorting version is clear and usually fast enough.

Subarray sum equals k: prefix sums plus a map

Module 2 previewed this pattern; here is why it works. Let running be the sum of all items so far. A subarray that ends at the current item sums to k exactly when some EARLIER running total equals running − k. So walk once, and at each step add the number of earlier prefixes equal to running − k. A dict from "prefix sum" to "times seen" answers that in O(1).

The trace is for nums = [1, 2, −1, 2] and k = 3. The two subarrays found are [1, 2] and [2, −1, 2]. The dict starts as {0: 1} for the empty prefix, which is how a subarray starting at index 0 gets counted.

def subarray_sum_count(nums, k):
    seen = {0: 1}
    running = count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)    # look up first...
        seen[running] = seen.get(running, 0) + 1   # ...then store
    return count

print(subarray_sum_count([1, 2, -1, 2], 3))   # Output: 2

Look up BEFORE storing the current running total. Otherwise, when k = 0, every prefix would match itself and count an empty subarray.

Common mistakes

• counts[w] += 1 on a plain dict for a new key raises KeyError. Fix: counts.get(w, 0) + 1, defaultdict(int) or Counter.
• Using a list or a set as the group key. Fix: a sorted string or a tuple of counts.
• No tie rule in top-k, so the output can change between programs or languages. Fix: sort by (−count, item) and say the rule aloud.
• In subarray-sum, forgetting seen = {0: 1}, or storing running before looking it up. Fix: start with the empty prefix; look up first, then store.
• Returning groups in whatever order the dict gives when the task asks for a fixed order. Fix: sort exactly as the task says.