Arrays and hashing

A hash map (Python's dict) finds, adds and removes a key in O(1) time on average. Whenever a solution keeps asking "have I seen this before?" or "how many times?", a hash map or set is the answer.

Two sum

Given a list and a target, find the positions of two numbers that add up to the target.

The brute force tries every pair: O(n²). Better: walk through the list once, and for each number x, ask whether its complement target − x has already been seen. A dictionary remembers each number's position.

def two_sum(nums, target):
    position = {}                     # number -> where we saw it
    for i, x in enumerate(nums):
        need = target - x
        if need in position:          # its partner came earlier
            return position[need], i
        position[x] = i
    return None

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

O(n) time and O(n) space. Notice that the dictionary is checked before x is added, so x is never paired with itself.

Counting

"How often does each item appear?" is a dictionary of counts:

counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1

collections.Counter(words) does the same in one line, and Counter.most_common(k) gives the k most frequent.

Grouping: anagrams

Group words that are anagrams of each other (the same letters in another order: "listen", "silent").

Two words are anagrams exactly when their sorted letters are the same, so the sorted letters make a perfect dictionary key:

def group_anagrams(words):
    groups = {}
    for word in words:
        key = "".join(sorted(word))       # "listen" -> "eilnst"
        groups.setdefault(key, []).append(word)
    return list(groups.values())

print(group_anagrams(["listen", "silent", "enlist", "google", "inlets", "banana", "gogole"]))

The general trick: find a key that is the same for everything that belongs together. Sorted letters work here; a tuple of 26 letter counts is faster for long words.

Prefix sums

To answer many "sum of a[i..j]" questions, precompute prefix sums: prefix[k] = a[0] + ... + a[k − 1]. Then sum(a[i..j]) = prefix[j + 1] − prefix[i], each in O(1). Combined with a hash map, prefix sums also count subarrays with a given sum in O(n): a subarray ending here sums to k exactly when an earlier prefix equals (current prefix − k).

Mark lesson complete