Classic Hash Tricks: Two Sum and Friends

Two Sum

Find two positions in an (unsorted) list whose numbers add up to a target. The trick: for each number x, the partner we need is target - x. Remember every number we've passed in a dictionary (number → index), and check if the partner is already there:

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

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))

Output

(0, 1)
(1, 2)

Think of it like this: At a party you need someone whose shirt colour matches yours. Instead of asking everyone again each time a new person arrives, you keep a guest book of colours already in the room.

First letter that appears only once

from collections import Counter

def first_unique(s):
    count = Counter(s)
    for i, ch in enumerate(s):
        if count[ch] == 1:
            return i
    return -1

print(first_unique("leetcode"))
print(first_unique("aabb"))

Output

0
-1

Two passes over the string: O(n).

Group things by a key

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = {}
for w in words:
    key = "".join(sorted(w))       # anagrams share the same sorted letters
    groups.setdefault(key, []).append(w)
print(list(groups.values()))

Output

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Remember: If you catch yourself writing a loop inside a loop just to find something, ask: “could a dict or set remember it for me?”