PART 4 · DSA AND COMPLEXITY · CHAPTER 19

Hashing: two-sum, anagrams, subarray sums

FreeLesson 44 of 78

A hash map answers "have I seen this before?" in O(1). Most medium problems become easy once you ask what to store in it.

In plain words: a dict turns a key into a number (the hash) and uses it to jump straight to a slot. No scanning. The cost is memory: one slot per key, plus spare room so slots stay mostly empty.

TWO-SUM AND GROUP ANAGRAMSPYTHON 3.12

def two_sum(nums, target):           # unsorted input
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None

print(two_sum([1198, 796, 1499, 1999, 1348], 2847))

from collections import defaultdict
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)    # same letters, same key
    return list(groups.values())

words = ["listen", "silent", "enlist", "data", "tada", "etl"]
print(group_anagrams(words))

Output

(2, 4)
[['listen', 'silent', 'enlist'], ['data', 'tada'], ['etl']]

PREFIX SUM + HASH MAP, AND FIRST UNIQUEPYTHON 3.12

from collections import Counter

def subarrays_with_sum(nums, k):
    count, running = 0, 0
    seen = Counter({0: 1})              # prefix sum -> how many times
    for x in nums:
        running += x
        count += seen[running - k]      # earlier prefixes that leave k
        seen[running] += 1
    return count

print(subarrays_with_sum([1, 2, 3, -1, 1, 2], 3))

def first_unique(stream):
    counts = Counter(stream)
    return next((x for x in stream if counts[x] == 1), None)

print(first_unique(["u2", "u1", "u2", "u3", "u1"]))

Output

4
u3

Store in the map...	To answer	Example
value -> index	"Where is the partner?"	Two-sum
sorted letters -> words	"Which items are equivalent?"	Group anagrams, normalised addresses
item -> count	"How many / first unique / most common?"	Counter, first non-repeating
prefix sum -> count	"How many ranges add to k?"	Subarray sum equals k
id -> latest record	"What is the current state?"	Dedupe, CDC (P4)

Practice before you move on

Use a dict to find two orders whose amounts add up to a target in a single pass.
Find the first customer_id in orders.csv that appears exactly once.