02 · Count work, then remember what matters

The notebook receives thousands of durations. Two questions sound similar but need different retained information: “How often did each job run?” and “How many contiguous ranges have total duration exactly a target?” Start with the question, not with a slogan such as “hashmaps solve everything.”

A cost model is an explicit simplification

Let n be the number of records. Scanning each once performs n visits. Comparing each unordered pair performs n(n-1)/2 comparisons: for each position, count only the positions after it. At n = 1000, that is 499,500 pairs; at n = 2000, it is 1,999,000. Growth is approximately fourfold, not a prediction of fourfold wall-clock time on every machine.

Big-O is an asymptotic upper bound under a chosen operation model. Saying a pair scan is O(n²) does not specify seconds, cache behavior or a fixed interpreter throughput. A tight bound is Θ(n²). An O(n) upper bound does not assert that every input takes exactly the same time. Separate worst-case, expected and amortized claims: “expected” assumes an input or hashing model; “amortized” spreads costs over an operation sequence, even if a particular operation is expensive.

A dictionary avoids scanning all prior keys by using hashing to locate candidate storage positions, then equality to resolve candidates. In the usual well-behaved hashing model, operations take expected constant time for bounded-size keys; this is not a language-level worst-case guarantee. Long strings, arbitrary Python __hash__ or __eq__ implementations, and adversarial collisions invalidate the unit-cost shortcut. Our examples use small integers and short strings. MIT’s hashing notes separate collisions, load factor and expected amortized operations; those model assumptions should not be mistaken for a worst-case promise about arbitrary Python objects.

Counts are sufficient state for a frequency query

The official Counter documentation specifies a dictionary subclass for hashable objects and a zero count for missing keys. It also warns that setting a count to zero does not remove the key. Those are semantics; they do not prove that our chosen state answers a particular problem.

from collections import Counter
 
jobs = ["ingest", "validate", "ingest", "publish"]
counts = Counter(jobs)
assert counts["ingest"] == 2
assert counts["missing"] == 0
assert sum(counts.values()) == len(jobs)
counts["unused"] = 0
assert "unused" in counts

After processing a prefix, the invariant is: for every job name, its count equals the number of its occurrences in that prefix. Initially every count is zero. Reading one name changes only that name's count by one, preserving the statement. At the end the prefix is the whole sequence. Time is expected O(n), additional space O(d) for d distinct names, under the assumptions above. Retaining every record would be unnecessary for this query, but necessary for some later questions about order.

Prefix sums turn ranges into two boundaries

Define prefix[0] = 0 and prefix[j] as the sum of elements before index j. Then the half-open interval [i, j) has sum prefix[j] - prefix[i]: the prefix before i occurs in both totals and cancels. An empty interval has i == j and sum zero. The sentinel zero avoids a special case for a range starting at index zero.

def prefixes(values):
    result = [0]
    for x in values:
        result.append(result[-1] + x)
    return result
 
values = [4, -2, 7, 1]
p = prefixes(values)
assert p == [0, 4, 2, 9, 10]
assert p[3] - p[1] == 5  # values[1:3] is [-2, 7]
for i in range(len(values) + 1):
    for j in range(i, len(values) + 1):
        assert p[j] - p[i] == sum(values[i:j])

Building the table costs O(n) additions and O(n) storage; each subsequent range query costs one subtraction. Mutating an early input invalidates later prefixes. This representation trades update work for query work; it is not a universal “fast array.” Python slicing also creates a new list, so the oracle's sum(values[i:j]) is intentionally slow, not the implementation to use for every large query.

Count ranges without retaining all boundaries

To count nonempty ranges with sum target, rearrange the equation to prefix[i] = prefix[j] - target. While visiting a new right boundary, we only need the frequencies of earlier prefix totals. Query before inserting the current prefix: inserting first would count an empty interval whenever the target is zero.

from itertools import product
 
 
def count_ranges(values, target):
    seen = {0: 1}
    total = answer = 0
    for x in values:
        total += x
        answer += seen.get(total - target, 0)
        seen[total] = seen.get(total, 0) + 1
    return answer
 
 
def brute_ranges(values, target):
    return sum(
        sum(values[i:j]) == target
        for i in range(len(values))
        for j in range(i + 1, len(values) + 1)
    )
 
assert count_ranges([1, -1, 1], 1) == 3
assert count_ranges([0, 0], 0) == 3
assert count_ranges([], 0) == 0
for n in range(6):
    for values in product((-1, 0, 1), repeat=n):
        for target in range(-2, 3):
            assert count_ranges(values, target) == brute_ranges(values, target)

For [1, -1, 1], prefix totals are 0, 1, 0, 1. The final total 1 needs earlier totals 0 to make target 1; there are two. The previous 1 already contributed one, producing three ranges. A set would lose the multiplicity of the two zeros. Negative inputs cause no problem because the derivation uses equality, not a monotone window.

The algorithm performs expected O(n) dictionary work and uses O(n) additional entries in the worst case. Python integers can grow beyond machine words; addition and hashing of arbitrarily large integers are not constant time. The stated bound counts arithmetic and mapping operations rather than bit operations. The Python tutorial supplies the mapping and key model; the range identity and correctness argument here are derived algebraically and checked against the separate oracle, not quoted from that API reference.

Exercises

1. Why is seen = {0: 1} necessary? Give a one-element counterexample without it.
2. For n zeros and target zero, derive the exact answer without running the algorithm.
3. You need one update and one range query per request. Why might a prefix array no longer be the right representation?

Exit artifact: a slow oracle, an optimized implementation, a loop invariant, and an explicit key-cost assumption. A passing bounded exhaustive test is powerful regression evidence, not a proof for every length.

Next: Search and sliding windows.