DSA & CS / 2. HASH MAPS & SETS

Hash Maps & Sets

O(1) lookup — the most versatile tool in your arsenal

EXPLANATION

A Hash Map (dict in Python) maps keys to values using a hash function. Average O(1) for insert, lookup, delete. Worst case O(n) due to collisions, but rare.

Hash Set is a hash map where you only care about keys (values are irrelevant). O(1) membership testing.

When to reach for a hash map:
• Counting frequencies → Counter or defaultdict(int)
• Grouping items → defaultdict(list)
• Checking if element seen before → set
• Caching computed results → dict (manual memoization)
• Two Sum / complement problems → store seen values

The classic trick: instead of nested loop to find pairs, store what you've seen in a hash map and check if the complement exists in O(1).

Python tools:
• dict → general hash map
• defaultdict → auto-initializes missing keys
• Counter → frequency counting with extras (most_common, etc.)
• set → O(1) membership, union, intersection

DIAGRAM

Hash Map internal:
  key → hash(key) % bucket_count → bucket index
  "apple" → hash("apple") % 8 → bucket 3 → value: 5

  Collision: two keys → same bucket → chaining (linked list)

  Counter use case — anagram check:
  "listen" → {l:1, i:1, s:1, t:1, e:1, n:1}
  "silent" → {s:1, i:1, l:1, e:1, n:1, t:1}
  same Counter → anagram ✓

  Two Sum trick:
  seen = {}
  for each num: if (target - num) in seen → found pair
               else: seen[num] = index

CODE

PYTHON
1from collections import defaultdict, Counter
2
3# ── Two Sum (classic hash map) ────────────────────────────────────
4def two_sum(nums: list[int], target: int) -> list[int]:
5    seen = {}   # value → index
6    for i, num in enumerate(nums):
7        complement = target - num
8        if complement in seen:
9            return [seen[complement], i]
10        seen[num] = i
11    return []
12
13# ── Group Anagrams ────────────────────────────────────────────────
14def group_anagrams(strs: list[str]) -> list[list[str]]:
15    groups = defaultdict(list)
16    for s in strs:
17        key = tuple(sorted(s))   # "eat" → ('a','e','t')
18        groups[key].append(s)
19    return list(groups.values())
20
21# ── Top K Frequent Elements ───────────────────────────────────────
22def top_k_frequent(nums: list[int], k: int) -> list[int]:
23    count = Counter(nums)
24    return [x for x, _ in count.most_common(k)]
25
26# ── Longest Consecutive Sequence — O(n) ──────────────────────────
27def longest_consecutive(nums: list[int]) -> int:
28    num_set = set(nums)
29    best = 0
30    for num in num_set:
31        if num - 1 not in num_set:     # only start from sequence head
32            length = 1
33            while num + length in num_set:
34                length += 1
35            best = max(best, length)
36    return best
37
38# ── Subarray Sum Equals K (prefix sum + hashmap) ──────────────────
39def subarray_sum(nums: list[int], k: int) -> int:
40    count = 0
41    prefix = 0
42    seen = defaultdict(int)
43    seen[0] = 1                        # empty prefix
44    for num in nums:
45        prefix += num
46        count += seen[prefix - k]      # how many times (prefix-k) seen
47        seen[prefix] += 1
48    return count
49
50# Tests
51print(two_sum([2, 7, 11, 15], 9))                    # [0, 1]
52print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
53print(top_k_frequent([1,1,1,2,2,3], 2))              # [1, 2]
54print(longest_consecutive([100,4,200,1,3,2]))         # 4
55print(subarray_sum([1,1,1], 2))                       # 2
← PREV1. Arrays & Two PointersNEXT →3. Stacks & Queues