Hash Maps

In plain English: Find two numbers in an unsorted list that add up to a target and return their indices.

Instead of checking all pairs O(n²), store each value in a hashmap — then lookup for the complement is O(1).

Prompt

Given unsorted array a and target t, return indices of the pair that sums to t.

Solution

def two_sum(a, t):
    seen = {}
    for i, x in enumerate(a):
        # check complement before storing
        if t - x in seen:
            return [seen[t - x], i]
        seen[x] = i
    return []

# Test: two_sum([2,7,11,15], 9) == [0, 1]

Related Micro Drills

254 Complement map (two sum) Hash Strategies 10s

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

104 Longest substring no repeats Sliding Window 15s

Hash-map window tracks last index of each char. Avoids set removal on duplicates.

seen = {}
l = res = 0
for r, c in enumerate(s):
    if c in seen and seen[c] &gt;= l:
        l = seen[c] + 1
    seen[c] = r
    res = max(res, r - l + 1)

194 Partition to K equal sum subsets Backtracking 15s

Try placing each number into k buckets. Prune: skip if bucket overflows, skip symmetric bucket states.

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k: return False
    target = total // k
    nums.sort(reverse=True)
    buckets = [0] * k

    def backtrack(i):
        if i == len(nums): return all(b == target for b in buckets)
        seen = set()
        for j in range(k):
            if buckets[j] + nums[i] &gt; target: continue
            if buckets[j] in seen: continue  # prune symmetric
            seen.add(buckets[j])
            buckets[j] += nums[i]
            if backtrack(i + 1): return True
            buckets[j] -= nums[i]
        return False
    return backtrack(0)

Drill #23 — Two sum (unsorted)

Related Micro Drills