Why is `x in my_list` O(n), and how do you fix a loop that tests it repeatedly?
answer
- The list has no index over its contents
- Cost depends on where the match sits
- A membership test inside a growing loop
- Hash the container once, before the loop
basics
~20 sA list keeps no index of its contents, so in walks it element by element — O(n). Running that test once per item of another collection is O(n²); build a set or dict once, before the loop, for O(1) average lookups.
solid answer
~50 s`in` on a list is a linear scan: the list is a contiguous array of object pointers with no hash index, so membership compares element after element until it finds a match, and an **absent** value always costs a full pass. `list.index()` and `list.count()` scan the same way. One scan is fine; a scan per item of a loop turns an O(n) job into O(n²). The fix is to hash: build a `set` (or a `dict` if you also need values) **once before the loop**, then test with `in` against that — O(1) average, at the cost of one O(n) build and the requirement that elements be hashable. If order matters use `dict.fromkeys(...)` to dedupe while preserving insertion order; if elements are unhashable but orderable, sort once and use `bisect.bisect_left`. For a list of a handful of items the linear scan is genuinely faster — do not hash reflexively.
code
python · 11 linesimport timeit
haystack = list(range(200_000))
probes = list(range(0, 200_000, 2_000))
list_time = timeit.timeit(lambda: [p in haystack for p in probes], number=1)
seen = set(haystack)
set_time = timeit.timeit(lambda: [p in seen for p in probes], number=1)
print(f"list scan: {list_time:.4f}s")
print(f"set lookup: {set_time:.6f}s")go deeper
Remember the ranking: membership on a list walks the whole thing, membership on a set or dict is effectively constant time. Be able to say which container you would reach for when the same lookup runs many times.
Explain the mechanics: a contiguous array with no hash index, identity-then-equality comparison per slot, the absent-value worst case, and the O(n²) total when the test sits inside a loop over comparable data.
Demonstrate diagnosis and constraints: spot the accidental quadratic in review, hoist the set build out of the loop, and handle unhashable elements with a tuple projection or a sorted list plus bisect.
Own the tradeoff: hashing buys lookup speed with memory, hashability requirements and the loss of order, so the decision is about the data's identity model and lifetime, not a reflex to convert every list to a set.
### Why the scan is linear A CPython list is a contiguous array of pointers to objects, in insertion order, with nothing resembling a hash index. Evaluating `x in lst` calls the list's membership implementation, which loops over the slots from index 0 and compares each element to `x`. Cost is proportional to the *position* of the match, and a value that is **not** present is the worst case: every element is compared before the answer `False` comes back. `list.index()` and `list.count()` share this shape — `count` always walks the whole list because it cannot stop early. The comparison itself is subtler than it looks: each slot is checked for **identity first, then equality**. That is why an object that is not equal to itself can still be found in a list that contains it: ```pycon >>> nan = float("nan") >>> nan == nan False >>> nan in [nan] True >>> nan in [float("nan")] False ``` Equality is also user code: if the elements define `__eq__`, every probe runs that method, so a “linear” scan over rich objects can be far more expensive per step than a scan over integers. ### The quadratic loop The interview version of this is a de-duplication or filtering loop. Consider a batch of geocoding results being merged into a store of addresses already seen: ```python seen = [] for record in batch: if record["address"] not in seen: # O(len(seen)) every iteration seen.append(record["address"]) ``` Every iteration rescans a list that is itself growing, so the total work is roughly n²/2 comparisons. At a thousand addresses nobody notices; at the backlog that accumulated across a 3-week release train it is the difference between seconds and hours, and the symptom is the classic one — “it worked in the test fixture and hung in production”, with CPU pinned at 100% on one core and no error anywhere. ### The fix A `set` is a hash table: membership hashes the probe and looks in one bucket, O(1) on average, independent of size. Hoist the build out of the loop — rebuilding it inside the loop reproduces the quadratic behaviour with a bigger constant. ```python seen = set() keep = [] for record in batch: address = record["address"] if address not in seen: seen.add(address) keep.append(address) ``` The cost model changes from O(n²) to O(n) plus the memory of the set. Three constraints come with it: 1. **Elements must be hashable.** Lists and dicts are not; a tuple of the fields you care about usually is, so key the set on `(record["lat"], record["lon"])` rather than on the raw record. A class that defines `__eq__` without `__hash__` becomes unhashable, because Python sets `__hash__` to `None` in that case. 2. **A set has no order and no duplicates.** If the deduplicated output must keep first-seen order, either keep the parallel list as above, or use `list(dict.fromkeys(items))` — dicts have preserved insertion order since 3.7, which is what makes that idiom safe. 3. **Building the set is itself O(n).** For a single membership test against a list you will only touch once, the scan wins outright; for a short list — on the order of ten items — the linear scan is also faster in practice, because hashing has a real per-probe constant. ### When hashing is not available If the elements cannot be hashed but can be ordered, sort once and use the `bisect` module: `bisect.bisect_left` gives an O(log n) position, and comparing the element there answers membership. If lookups are by one field of a record, the right structure is usually a `dict` keyed on that field, which answers membership *and* retrieves the row in one step. ### What an interviewer is actually testing Two things. First, that you know the cost model of the built-in containers rather than treating them as interchangeable bags. Second, that you can spot the accidental quadratic in code — a membership test, a `list.index()` call, or a `remove` sitting inside a loop over data of the same order. That pattern is the single most common performance defect in otherwise correct Python, precisely because it is invisible at test-fixture sizes.
- Why does `nan in [nan]` return True when `nan == nan` is False?List membership checks each slot for identity first and only falls back to `==` when the objects are not the same object. The same `nan` object is found by the identity check, so the result is `True`. A *different* `nan` object fails both checks, so `nan in [float("nan")]` is `False`. The same shortcut applies to `list.index()`, `count()` and `remove()`.
- The elements are dictionaries, so a set is not an option. What do you do?Hash a projection instead of the object: build a set of the tuple of fields that define identity, for example `(rec["lat"], rec["lon"])`, and test membership against that. If a lookup rather than a yes/no is wanted, use a dict keyed on that tuple. If the records cannot be hashed at all but can be ordered, sort once and use `bisect.bisect_left` for O(log n) probes.
- Is converting a list to a set always the right call for membership tests?No. Building the set costs O(n) and memory, so a single test against a list you touch once is cheaper as a scan. For very short lists — around ten items — the linear scan also wins on constants. And a set drops duplicates and order, which may be information you needed. Convert when the same container is probed many times.
saying these in an interview costs you the question
- Claims `in` on a list is O(1) like a dict lookup
- Rebuilds the set inside the loop each iteration
- Says a set preserves insertion order
- Assumes any object can be put in a set
- Thinks list.index() is faster than the `in` operator