A coffee shop gives at most one stamp per customer per day, however many coffees they buy that day. The till log is a list of (day, customer) purchases, not in any particular order.
Write free_coffee(log: list[tuple[int, str]], k: int) -> list[str] that returns the customers who have earned at least k stamps (visited on at least k different days), sorted alphabetically.
log = [(1, "ivy"), (1, "ivy"), (2, "raj"), (3, "ivy"), (1, "raj"), (2, "ivy")]
free_coffee(log, 3) # ["ivy"] ivy: days {1, 2, 3}; raj: days {1, 2}
free_coffee(log, 2) # ["ivy", "raj"]
free_coffee([], 1) # []
0 <= len(log) <= 2 * 10^5; days are in[1, 10^9];1 <= k <= 10^5; names are non-empty lowercase words.- Scanning the whole log again for each customer is O(n × customers). The tests include a large log with tens of thousands of customers, so do one pass.
Show hint
map each customer to a set of the days they visited (a defaultdict(set) is handy); repeat purchases on the same day then disappear on their own, and len of each set is the stamp count.