Hashing patterns: counting, pairs and grouping

Three hashing patterns solve a large share of counting and lookup problems. Counting keeps a frequency map from each value to how many times it has appeared. Complement lookup finds partners: for a value x and a target sum, the only partner is target − x, and one map lookup finds it. Grouping maps each item to a canonical key, such as its letters in sorted order, so that items that belong together share one key. This lesson works through a problem that needs the first two at once, counting the pairs that add up to a target when values repeat, and then applies the same tools to grouping, consecutive runs and subarray sums.

The problem: legs that make a connection

Three examples:

1. legs = [90, 150, 60, 120, 90, 150] and target = 240 give 4: each of the two 90s pairs with each of the two 150s. The single 120 cannot pair with itself.
2. legs = [100, 100, 100] and target = 200 give 3, one connection for each two of the three legs.
3. legs = [45] and target = 90 give 0.

When every leg fits every other, the answer is n(n − 1)/2, which for 200,000 legs is 19,999,900,000: more than nine times 2,147,483,647, the largest signed 32-bit integer.

The brute force, and why it is too slow

Try every pair: for each leg j, check every earlier leg i. It is plainly correct, which makes it the reference for testing faster code, but it checks all n(n − 1)/2 pairs:

"""Every pair of legs, checked one by one, and how much CPU time that takes as the timetable grows."""
import random
import time


def count_connections_brute(legs, target):
    count = 0
    for j in range(len(legs)):
        for i in range(j):
            if legs[i] + legs[j] == target:
                count += 1
    return count


print(count_connections_brute([90, 150, 60, 120, 90, 150], 240))
print(count_connections_brute([100, 100, 100], 200))
print(count_connections_brute([45], 90))

rng = random.Random(1)
per_pair = None
for n in (1_000, 2_000):
    legs = [rng.randrange(30, 600) for _ in range(n)]
    start = time.process_time()
    count_connections_brute(legs, 600)
    seconds = time.process_time() - start
    pairs = n * (n - 1) // 2
    per_pair = seconds / pairs
    print(f"n = {n:,}: {pairs:,} pairs checked in {seconds * 1000:,.0f} ms")
n = 200_000
print(f"n = {n:,}: {n * (n - 1) // 2:,} pairs, about {n * (n - 1) // 2 * per_pair / 60:,.0f} minutes at that speed")

4
3
0
n = 1,000: 499,500 pairs checked in 19 ms
n = 2,000: 1,999,000 pairs checked in 80 ms
n = 200,000: 19,999,900,000 pairs, about 13 minutes at that speed

Doubling the timetable multiplies the work by four. At the limit of 200,000 legs that is about 2 × 10¹⁰ pairs, about 13 minutes of CPython in the recorded run, and still tens of seconds in a compiled language at about 10⁹ simple checks a second.

What to notice: for a leg of d minutes, exactly one duration completes it, target − d. The brute force asks every earlier leg, one at a time, whether it has that duration, but the answer needed is only how many earlier legs do.

Counting pairs in one pass, with the invariant that proves it Pro: opens with a Pro, Premium or Ultimate pass