Customers Who Never Order Solution

Problem

You are given two lists: customers, where each entry is [customer_id, name], and orders, where each entry is [order_id, customer_id]. Return the names of every customer whose ID never appears in orders, in the same order they appear in customers.

Example:

Input: customers = [[1,"Alice"],[2,"Bob"],[3,"Carol"],[4,"Dan"]], orders = [[100,2],[101,4],[102,2]]
Output: ["Alice", "Carol"]
Explanation: Bob (id 2) and Dan (id 4) placed orders; Alice (id 1) and Carol (id 3) never appear in orders, so their names are returned.

Intuition

For each customer, we only need to answer one question: does this customer's ID appear anywhere in orders? Repeating a linear scan of orders for every customer wastes work, so we pay one pass to convert orders into a data structure that answers "does id X appear?" in O(1), then check each customer against it.

Approach 1 — Brute Force

For each customer, scan the entire orders list looking for a matching customer ID. If none is found, add the name to the result.

Steps:

Iterate through each (customer_id, name) in customers
For each one, scan every (order_id, ordered_customer_id) in orders
If no ordered_customer_id equals customer_id, append name to the result
Return the result

1def customersWhoNeverOrder(customers, orders):
2    result = []
3    for customer_id, name in customers:
4        placed_order = False
5        for _, ordered_customer_id in orders:
6            if ordered_customer_id == customer_id:
7                placed_order = True
8                break  # one match is enough to disqualify this customer
9        if not placed_order:
10            result.append(name)
11    return result

Time: O(n · m) — for each of n customers we scan up to m orders
Space: O(1) — no auxiliary structures beyond the output list

Approach 2 — Hash Set (Optimal)

Collect every customer ID that appears in orders into a hash set once, then check each customer's ID against the set in O(1).

Steps:

Build customers_with_orders, a hash set of every customer_id in orders
Iterate through customers in the given order
If a customer's ID is not in the set, append their name to the result
Return the result

1def customersWhoNeverOrder(customers, orders):
2    # one pass collects every customer id that placed at least one order
3    customers_with_orders = {ordered_customer_id for _, ordered_customer_id in orders}
4
5    result = []
6    for customer_id, name in customers:
7        # membership check is O(1), so total work is linear in customers + orders
8        if customer_id not in customers_with_orders:
9            result.append(name)
10    return result

Time: O(n + m) — one pass over orders to build the set, one pass over customers to filter
Space: O(m) — the set holds at most one entry per distinct customer ID in orders

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n · m)	O(1)	Only when memory is tight and inputs are tiny
Hash Set	O(n + m)	O(m)	Default choice — the standard "does X exist in this collection?" pattern

Common Mistakes

Inverting the filter and returning customers who did order: the check is not in set, not in set. It's easy to write the wrong branch when the natural way to build the set is from orders.
Using a list instead of a set for customers_with_orders: Python's in on a list is O(m), silently regressing the hash approach back to O(n · m). Always use a set (or dict) when the only operation is membership testing.
Building the set from the wrong list: putting customer IDs into a set and checking each order against it tells you which orders reference a real customer, which is the opposite question. The set must be built from orders.
Returning customer IDs instead of names: the problem asks for names. When the two are stored in the same row it's easy to append(customer_id) by reflex.
Deduplicating results manually: each customer appears once in customers, so their name can be added at most once — no dedup pass is needed. Adding one hides a bug where the same customer was iterated twice.

Customers Who Never Order — Solution