1.2.25 · D2Introduction to Programming (Python)

Visual walkthrough — Sets — unique elements, set operations (union, intersection, difference)

3,616 words16 min readBack to topic

We will use exactly one running example the whole way down:

Read that as: box holds the labels 1, 2, 3, 4, and box holds 3, 4, 5, 6. The curly braces { } are just fence-posts around a collection. That's all a set looks like on paper.


Step 1 — A set is a wall of pigeonholes, not a line of boxes

PICTURE (s01): on the left, the list — four numbered boxes in a row. On the right, the set — a scattered grid where 1, 2, 3, 4 sit in seemingly random holes. No [0], no [1]. Just presence.


Step 2 — The address is hash(x): turning a value into a location

PICTURE (s02): the value 3 enters a funnel labelled hash, out drops a big number, then mod N bends the arrow into bucket #2 of the grid. A second arrow shows 3 entering again later and landing in the same bucket — this repeatability is the whole point.


Step 3 — When two values want the same hole: collisions

PICTURE (s03): value 13 and value 3 both compute bucket #2. Under chaining, bucket #2 holds a mini-list [3, 13]; a magnifier shows the equality check newcomer == 3? walking that list. Under open addressing, 13 bounces one slot down to the next empty hole (arrow).


Step 4 — WHY uniqueness is automatic (and free)

Let be the number of elements. Then:

PICTURE (s04): two adds. Adding 5 (empty bucket) → it drops in, green check. Adding 3 again (bucket already holds 3) → red "STOP, already here", the duplicate evaporates. The grid still shows one 3.


Step 5 — Keeping it fast forever: resizing and rehashing

PICTURE (s05): left grid () filling past the 2/3 line (red hatching). An arrow "RESIZE + REHASH" points to a right grid (), where the same values have been recomputed and scattered anew into more, emptier holes.


Step 6 — Two sets side by side: everything is now a membership question

PICTURE (s06): two circles overlapping. Left crescent = only-A = {1,2} (blue). Lens middle = both = {3,4} (yellow). Right crescent = only-B = {5,6} (red). Outside both, faint "neither: everything else" text. Each element sits in its zone as a labelled dot.


Step 7 — Union A | B: keep every zone that touches either circle

For our example: .

PICTURE (s07): both circles fully shaded green; dots 1–6 all inside; a callout notes 3,4 counted once.


Step 8 — Intersection A & B: keep only the overlap

For our example: .

PICTURE (s08): only the central lens shaded yellow; dots 3,4 highlighted; crescents dimmed.


Step 9 — Difference A - B: keep A's crescent only (and why it's lopsided)

PICTURE (s09): two panels. Left: A - B shades only the left crescent {1,2}. Right: B - A shades only the right crescent {5,6}. A red arrow between them screams "not the same."


Step 10 — Symmetric difference A ^ B: keep both crescents, drop the middle

For our example: .

PICTURE (s10): both crescents shaded (blue + red), the middle lens carved out and greyed with a scissors icon; dots 1,2,5,6 kept, 3,4 crossed out.


Step 11 — The degenerate cases (never let the reader hit an unshown scenario)

Three edge cases, each a mini-picture:

  1. Empty (): overlap and B-crescent vanish. Union/difference/symdiff leave alone; intersection collapses to nothing (there's nothing to share).

  2. Identical sets (): the circles land perfectly on top of each other — all middle, no crescents. Both differences empty out, because "in A but not A" and "in exactly one" are impossible.

  3. Disjoint sets (no shared value): the circles don't overlap — no middle, only crescents. With nothing shared, "exactly one of them" is just "either of them."

PICTURE (s11): three small Venn panels: (a) one circle + a dot-less ghost circle, (b) two circles fully coincident, (c) two circles far apart. Each labelled with the collapsed result.


The one-picture summary

One Venn diagram, four coloured overlays stacked as a legend: union = all shaded, intersection = lens, difference = left crescent, symmetric difference = both crescents. Below it, the Boolean spine: |→OR→union, &→AND→intersection, -→AND-NOT→difference, ^→XOR→symmetric difference. That single card is the whole derivation.

Recall Feynman: the whole walkthrough in plain words

Picture a wall of empty pigeonholes. To store a number, you run it through a machine (hash) that always sends the same number to the same hole — so before dropping it in you just peek at its hole: if it's already there, you toss the duplicate. That one peek is why sets never repeat and why "is it in here?" is instant — you never walk the wall, you jump straight to the hole.

Two different numbers can point at the same hole — a collision — so the set keeps a tiny list there (or bounces you to the next free hole) and double-checks by actually comparing values. And as the wall fills up, the set quietly builds a bigger wall and re-files everyone (rehashing), so the holes stay mostly empty and lookups stay quick.

Now draw two overlapping bubbles, and . Every value falls into one of three visible pockets — only-A, the shared middle, only-B — plus a fourth "outside everything" pocket we never keep. The four operations are just which pockets you keep:

  • Union (|, OR): keep all three inside pockets — everything in either bubble.
  • Intersection (&, AND): keep only the middle — what they share.
  • Difference (A - B): keep only-A — and it's lopsided, B - A keeps the other crescent.
  • Symmetric difference (^, XOR, written ): keep both crescents, ditch the middle — "in exactly one."

And the corners: an empty bubble makes the middle disappear; two identical bubbles are all middle and no crescents; two far-apart bubbles have no middle at all. Nothing surprises you, because you can always just look at the picture.


Connections

  • Yeh note Hinglish mein
  • Lists — ordered, indexed collections — the ordered thing we traded away for speed
  • Dictionaries — key-value & why {} is a dict — why {} isn't an empty set
  • Hashing and Hashable Types — the machine behind Steps 2–5
  • Tuples — immutable sequences — valid (hashable) set elements
  • Big-O Notation & Time Complexity — where vs and amortized come from
  • Boolean Logic — AND, OR, XOR — the algebra behind the four operations