Optimisation Example: The Guests Who Came Both Years

A hash set finds the guests on both lists in time that matches reading the lists once, so speed cannot improve: only the memory can.

Optimising stops when the dominant step matches the best conceivable runtime, because no solution can be faster than reading its input, and the only improvement left is in memory. A wedding venue has last year's guest list, Ana, Ben, Cal, Dee, Eli and Fay, and this year's, Gus, Ben, Fay, Hal, Ana, Ivy and Jo, and wants the guests who came both years. Checking each name on one list against the whole other list is O(n · m) for lists of n and m names, and a hash set of last year's names removes that scan.

Can any approach be faster than the hash set?

No. Any unread name might be on both lists, so every name must be read: O(n + m), which the hash set already reaches. Only its O(n) memory can still be improved.

The listing builds the set from last year's list and keeps each name of this year's that is in it, then does the same with two pointers over the two lists in alphabetical order.

guests.pypy

last_year = ["Ana", "Ben", "Cal", "Dee", "Eli", "Fay"]
this_year = ["Gus", "Ben", "Fay", "Hal", "Ana", "Ivy", "Jo"]

seen = set(last_year)
both = sorted(name for name in this_year if name in seen)
print("hash set:", " ".join(both), f"({len(seen)} names stored)")

first, second = sorted(last_year), sorted(this_year)
i = j = 0
shared = []
while i < len(first) and j < len(second):
    if first[i] == second[j]:
        shared.append(first[i])
        i += 1
        j += 1
    elif first[i] < second[j]:
        i += 1
    else:
        j += 1
print("two pointers over sorted lists:", " ".join(shared))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

hash set: Ana Ben Fay (6 names stored)
two pointers over sorted lists: Ana Ben Fay

Both find Ana, Ben and Fay. Two pointers step through two sorted lists together, moving whichever points at the earlier name and keeping a name when both point at it, so they read each name once with O(1) extra memory. They need the lists already sorted, and sorting them first costs more time than the set ever did.

Ways to find the names on both lists
Approach	Time	Extra memory	Needs
Check each name against the other list	O(n · m)	O(1)	Nothing
A hash set of one list, then a scan of the other	O(n + m) on average	O(n)	Nothing
Two pointers over both lists	O(n + m)	O(1)	Both lists already sorted
Sort both, then two pointers	O(n log n + m log m)	The sort's	Nothing

The hash set reaches the best conceivable runtime, so the optimisation stops there for time. If the lists arrive sorted, as a register often does, two pointers keep the time and drop the memory; if they do not, sorting to save memory makes the solution slower. Answering O(log n) or O(1) for this problem comes from not asking what must be read.

Complexity Analysis
Performance

← → move through sections and cards