Counting, deduplication, and lookup with hash maps

The single most-used data structure in interview problems. dict and set give O(1) average lookup, insert, and delete — turning O(n²) brute-force solutions into O(n).

Pattern: count with Counter

from collections import Counter

# Find the most common element
counts = Counter(arr)
most_common, freq = counts.most_common(1)[0]

# Check if two strings are anagrams
def is_anagram(a: str, b: str) -> bool:
    return Counter(a) == Counter(b)

# Find first non-repeating character
def first_unique(s: str) -> int:
    counts = Counter(s)
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

Pattern: two-sum (canonical hash map use)

def two_sum(arr: list[int], target: int) -> tuple[int, int] | None:
    """Find indices of two numbers summing to target."""
    seen = {}   # value -> index
    for i, x in enumerate(arr):
        complement = target - x
        if complement in seen:
            return (seen[complement], i)
        seen[x] = i
    return None

O(n) single pass. The trick: while scanning, ask “have I seen the complement of this number?” If yes, done. Otherwise record.

Pattern: group by transformation

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))   # canonical form
        groups[key].append(w)
    return list(groups.values())

The signature/key is the transformation. Words → sorted letters; numbers → sign+abs; intervals → some normal form.

Pattern: dedup while preserving order

def dedup(arr: list[int]) -> list[int]:
    seen = set()
    result = []
    for x in arr:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

# Python ≥3.7 dict preserves order, so:
def dedup_compact(arr: list[int]) -> list[int]:
    return list(dict.fromkeys(arr))

Pattern: longest consecutive sequence

def longest_consecutive(arr: list[int]) -> int:
    s = set(arr)
    best = 0
    for x in s:
        if x - 1 not in s:        # only start counting at sequence beginnings
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best

O(n) by exploiting the set lookup. The “only start at beginnings” check (x-1 not in set) prevents O(n²).

Problem: top-K frequent elements

import heapq
from collections import Counter

def top_k_frequent(arr: list[int], k: int) -> list[int]:
    counts = Counter(arr)
    return [x for x, _ in counts.most_common(k)]

# Manual heap version (for understanding):
def top_k_heap(arr: list[int], k: int) -> list[int]:
    counts = Counter(arr)
    return heapq.nlargest(k, counts, key=counts.get)

Counter.most_common uses heapq.nlargest internally. For huge data, streaming with a min-heap of size K is O(n log k) instead of O(n log n).

Problem: subarray with given XOR

def count_subarrays_with_xor(arr: list[int], target: int) -> int:
    """Number of subarrays whose XOR equals target."""
    count = 0
    prefix_xor = 0
    seen = {0: 1}
    for x in arr:
        prefix_xor ^= x
        # We want prefix_xor ^ ? == target, i.e., ? = prefix_xor ^ target
        if prefix_xor ^ target in seen:
            count += seen[prefix_xor ^ target]
        seen[prefix_xor] = seen.get(prefix_xor, 0) + 1
    return count

Same prefix-sum idea (see 01_arrays_strings/03_prefix_sums.md) but with XOR instead of addition.

Pitfalls

• Hashing mutable types — [1, 2] is unhashable, can’t use as dict key. Convert to tuple.
• Floating-point keys — 0.1 + 0.2 is not the same float as 0.3 (see tricky_questions/17_floats_and_equality.md). Use Decimal or carefully chosen tolerance.
• Forgetting that set is unordered (officially). For ordered uniqueness, use dict.fromkeys or OrderedDict.
• Counting with defaultdict(int) vs Counter — both work; Counter has more methods (most_common, arithmetic).

Interview angle

• “When does a hash map turn O(n^2) into O(n)?” - whenever the inner loop is asking “have I seen this before” or “does the complement exist”. Two-sum on an unsorted array is the canonical case: store value-to-index as you go and look up target - x.
• “What must a key satisfy?” - hashable, which in practice means immutable and consistent: equal objects must have equal hashes for the lifetime of the key. Mutating an object after using it as a key makes it unfindable. See ../../02_python_core/23_eq_vs_hash.md.
• “Counter, defaultdict, or plain dict?” - Counter for frequency with most_common; defaultdict(list) for grouping; plain dict with setdefault when you want the default computed lazily. Knowing Counter exists saves several lines in interviews.
• “What’s the cost you’re trading?” - O(n) extra space, and worst-case O(n) lookup under adversarial hash collisions, though Python’s randomised hashing makes that a non-issue in practice.