Card 02/ 08
Compare Two Delivery Manifests: From Striking Items Off to Counting Them
Two lists should hold the same items in any order: striking each item off the other list costs n², and two maps of counts cost n.
Counting each list's items in a hash map checks that two lists hold the same items in two passes, where striking each item off the other list costs a search per item. A warehouse receives a shipment with two manifests, one written when it was packed and one when it was unloaded, and the question is whether they list the same items in any order. Packed: bolt, nut, washer, bolt, hinge. Unloaded: nut, bolt, hinge, washer, nut.
Do the two manifests list the same items?
No. The packed manifest has two bolts and one nut, and the unloaded one has one bolt and two nuts. Both hold five items of the same four kinds, which is why a glance says yes.
The brute force strikes items off. For each item in the first list, search the second list for it and cross it out; if it is missing, the lists differ. For a first list of n items and a second of m, each search can read the whole second list, so the cost is O(n × m) in the worst case: about 10¹⁰ steps for two manifests of 100,000 lines. The repeated work is that the second list is searched again for every item, though nothing about it changes that a map could not record once.
Counting removes the search. A map from each item to how many times it appears comes out the same for any two lists that hold the same items in any order, so it is a canonical form of the list: one representative shared by every ordering of it. Build one count map per list and compare the maps.
Striking offO(n × m) time
For each item of the first list, search what is left of the second list and remove the item. The second list is read again for every item.
CountingO(n + m) time on average
One pass over each list builds a map of counts, and the two maps are compared. Each list is read once.
Set side by side, the two count maps agree on washers and hinges and disagree on the other two kinds.
| Item | Count when packed | Count when unloaded |
|---|---|---|
| bolt | 2 | 1 |
| nut | 1 | 2 |
| washer | 1 | 1 |
| hinge | 1 | 1 |
The listing holds both versions and runs them on the manifests, then runs the counting version on two short lists that do match.
def same_items_strike(first: list[str], second: list[str]) -> bool:
remaining = list(second)
for item in first:
if item not in remaining:
return False
remaining.remove(item)
return not remaining
def counts(items: list[str]) -> dict[str, int]:
tally: dict[str, int] = {}
for item in items:
tally[item] = tally.get(item, 0) + 1
return tally
def same_items_count(first: list[str], second: list[str]) -> bool:
return counts(first) == counts(second)
first = ["bolt", "nut", "washer", "bolt", "hinge"]
second = ["nut", "bolt", "hinge", "washer", "nut"]
print("first:", counts(first))
print("second:", counts(second))
print("striking off:", same_items_strike(first, second))
print("counting:", same_items_count(first, second))
print("nut bolt against bolt nut:", same_items_count(["nut", "bolt"], ["bolt", "nut"]))first: {'bolt': 2, 'nut': 1, 'washer': 1, 'hinge': 1}
second: {'nut': 2, 'bolt': 1, 'hinge': 1, 'washer': 1}
striking off: False
counting: False
nut bolt against bolt nut: TrueBoth versions agree, and the count maps show where the manifests part: bolts and nuts. Counting costs O(n + m) time on average and O(k) extra space for k distinct items, against O(n × m) time for striking off. Comparing two maps compares their keys and counts, not their order, which is why the order the items were written in cannot change the answer.
← → move through sections and cards