vizlearn

When should you use a set instead of a list?

Interview QuestionsBy Updated

A set buys O(1) membership and pays for it by losing order and duplicates, and by requiring hashable elements. When you need the speed and the order, dict.fromkeys(seq) deduplicates in one pass and keeps insertion order.

Overview

What you gain and what you give up

Gain: membership in O(1) rather than O(n), and uniqueness enforced for free.

Give up: order, duplicates, indexing (s[0] is a TypeError), and the ability to hold unhashable elements. You cannot put a list in a set, though you can put a tuple.

Converting costs O(n), so a single membership test on a small list is not worth it. More than a couple of tests, or a large collection, and it is.

Dicts, sets & hashingConceptualEasy

Step through it

What to watch

  • The set is smaller: duplicates are gone, and so is the order.
  • dict.fromkeys keeps both the order and the O(1) lookup.
  • All three hold the same distinct values.

Say this out loud

"Sets are for membership and uniqueness - O(1) instead of O(n). They lose order and need hashable elements. If I need dedup with order I use dict.fromkeys, since dicts have kept insertion order since 3.7."

When should you use a set instead of a list?

What does a set give you that a list does not, and how do you deduplicate while keeping order?

Deduplicating three ways

set(seq) — fastest, order destroyed.

sorted(set(seq)) — deduplicated and in sorted order, which is not the same as original order and is often what people accidentally ship.

list(dict.fromkeys(seq)) — deduplicated in first-seen order, one pass, and the one to remember. Dicts have preserved insertion order since 3.7, so this is a guarantee rather than a trick.

The operators that replace loops

a & b intersection, a | b union, a - b difference, a ^ b symmetric difference, a <= b subset. Each replaces a loop with a membership test inside it — which is to say, each replaces an accidental O(n·m) with an O(n + m).

"Which users are in A but not B" is a - b. Writing that as a comprehension over a list is the most common form of the quadratic trap.

Run it in Python

The three deduplication idioms and what each does to order, the set operators against their loop equivalents, and the membership timing that motivates all of it.

sets.pyPython 3
Output
How the code works
  1. list(dict.fromkeys(items))Deduplicates in first-seen order, in one pass. The idiom worth memorising, and a language guarantee rather than an implementation detail since 3.7.
  2. sorted(set(items))Deduplicated and reordered. It looks like a tidy version of the previous line and quietly changes the output order, which is a real bug when the order carried meaning.
  3. {[1, 2]}A TypeError: set elements must be hashable for the same reason dictionary keys must be. A tuple works.
  4. set(big_a) & set(big_b)Two O(n) conversions and an O(min) intersection, against a comprehension that scans one list for every element of the other. The timing at the end is that difference.
Change one thing
  • Deduplicate a list of dictionaries. It raises — and the usual fix is to key on something hashable, such as an id or a tuple of fields.
  • Compare a.isdisjoint(b) with not (a & b). The first can stop at the first shared element instead of building the whole intersection.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Which deduplicates a list while preserving the original order?
  2. What can a list hold that a set cannot?
  3. 'Which items are in A but not in B' is best written as:





 Cheat sheet
When should you use a set instead of a list?
A set buys O(1) membership and pays for it by losing order and duplicates, and by requiring hashable elements. When you need the speed and the order, dict.fromkeys(seq) deduplicates in one pass and keeps insertion order.
INTERVIEW · vizlearn.in/interview/sets-versus-lists-and-deduplication.html
More in Interview
InterviewWhat happens if you modify a collection while looping over it?InterviewMemoisation: caching with a dictionaryInterviewImplement a hash map from scratchInterviewGroup records and invert a dictionary
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact