Count how many user ids appear in both lists in linear time
list_a and list_b each hold user ids. Return how many distinct users appear in both lists. Each list may contain duplicates, but a user counts once.
Aim for O(n + m) time — a nested loop that scans list_b for every id in list_a would be O(n * m) and too slow on millions of ids.
def count_common_users(list_a: list[int], list_b: list[int]) -> int:
# your code hereWrite the implementation.
Turn one list into a set, then count the other's distinct ids found in it — set membership is O(1), so the job is O(n + m). len(set(list_a) & set(list_b)) does it in one line. The trap is if x in list_b, which rescans the list each time.
- ✗Using
if x in list_binside a loop, giving O(n*m) - ✗Forgetting to de-duplicate ids within each list
- ✗Sorting when a set intersection is simpler and faster
- →Why does converting to a set change the complexity class?
- →How would you also return the ids, not just the count?
Convert both lists to sets and intersect them — Python does the whole thing in O(n + m), and the sets remove within-list duplicates for free.
def count_common_users(list_a, list_b):
return len(set(list_a) & set(list_b))For list_a = [1, 1, 2, 3] and list_b = [3, 3, 4, 2] the sets are {1, 2, 3} and {2, 3, 4}; their intersection {2, 3} has length 2. The if x in list_b version would rescan list_b for every id in list_a, turning an O(n) job into O(n * m).
