Hash Strategies

defaultdict eliminates key-existence checks. Simplifies grouping and adjacency list construction.

from collections import defaultdict
d = defaultdict(list)

Counter gives instant frequency maps. Powers anagram checks and top-k problems.

from collections import Counter
freq = Counter(a)

dict.get() avoids KeyError. Cleaner than try/except for missing-key scenarios.

d.get(k, 0)

Dict comprehensions build lookup tables in one line. Used for index maps and inversions.

{k: v for k, v in items}

Membership testing is O(1) in hash maps. Foundation for two-sum and duplicate detection.

if k in d:

Dict merging combines configurations or frequency maps. Python 3.5+ unpacking syntax.

merged = {**d1, **d2}

Dict inversion swaps keys and values for reverse lookups. Useful in encoding problems.

inv = {v: k for k, v in d.items()}

Grouping by computed key is the core of group-anagrams and bucket-sort approaches.

from collections import defaultdict
groups = defaultdict(list)
for item in items:
    groups[key_fn(item)].append(item)

Two-pass hash map maps old nodes to new clones. Second pass wires next/random.

d = {None: None}
n = head
while n:
    d[n] = Node(n.val)
    n = n.next
n = head
while n:
    d[n].next = d[n.next]
    d[n].random = d[n.random]
    n = n.next

OrderedDict gives O(1) get/put with LRU eviction. Classic system design building block.

from collections import OrderedDict
class LRU:
    def __init__(self, cap):
        self.cap = cap
        self.d = OrderedDict()
    def get(self, k):
        if k not in self.d: return -1
        self.d.move_to_end(k)
        return self.d[k]
    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)

Map each char to its last index. Extend partition end greedily.

last = {c: i for i, c in enumerate(s)}
res = []
start = end = 0
for i, c in enumerate(s):
    end = max(end, last[c])
    if i == end:
        res.append(end - start + 1)
        start = i + 1

HashMap = O(n) time, O(n) space. Sorting = O(n log n) time, O(1) space. Choose based on constraints.

HASHMAP vs SORTING FOR DUPLICATES
─────────────────────────────────
HASHMAP (Counter/set):
  + O(n) time
  + Preserves original order
  + Online: can process stream
  - O(n) extra space
  - Hash collisions (rare, but exist)

SORTING:
  + O(1) extra space (if in-place sort allowed)
  + Duplicates are adjacent → easy to skip
  + Natural for "kth largest" type problems
  - O(n log n) time
  - Destroys original order

DECISION:
  "Contains duplicate?"     → set, O(n)
  "Count occurrences?"      → Counter, O(n)
  "Find all duplicates?"    → Counter or sort
  "K most frequent?"        → Counter + heap
  "Remove duplicates?"      → set (unordered) or sort (ordered)
  "Group anagrams?"         → sorted string as key → HashMap

BOTH WORK for: two sum (hash O(n) vs sort O(n log n))
ONLY HASH for: subarray sum (prefix sum + hash)
ONLY SORT for: merge intervals, meeting rooms

Store what you've seen, check for the complement. Turns O(n^2) brute force into O(n). The fundamental hash map pattern.

seen = {}
for i, x in enumerate(a):
    if target - x in seen:
        return [seen[target - x], i]
    seen[x] = i

Two-pass frequency count: first pass counts, second pass finds the target. Works for first unique, most common, etc.

freq = {}
for c in s:
    freq[c] = freq.get(c, 0) + 1
for i, c in enumerate(s):
    if freq[c] == 1:
        return i

Trie insert walks/creates nodes per character, marks end. Search is identical but checks existence instead of creating.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.is_end = True

Wildcard '.' branches to all children. Without wildcards it's a straight walk — the DFS only fires on '.' characters.

def search(node, word, i=0):
    if i == len(word):
        return node.is_end
    if word[i] == '.':
        return any(search(ch, word, i+1)
                   for ch in node.children.values())
    if word[i] not in node.children:
        return False
    return search(node.children[word[i]], word, i+1)

Same as search but returns True when you reach the end of the prefix — no need to check is_end.

def starts_with(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return True