Sets and Set Operations

Table of Contents

1. What Is a Set?
2. Sets Versus Arrays
3. JavaScript's Set
4. Thinking in Venn Diagrams
5. Union, Intersection, Difference
6. Subsets and Symmetric Difference
7. Real Questions, Real Sets
8. Sets, Bit Flags, and SQL
9. Recipe: sets.js for mathlab
10. Try It Yourself

1. What Is a Set?

A set is a collection of distinct things, where only two questions matter:

• Is this thing in the set, or not?
• How many things are in it?

That is all. A set has no first item, no second item, and no duplicates. The set of tags on a blog post {css, js, html} is the same set as {html, css, js}. Writing js twice does not make it more of a member.

Computer science loves sets because so many real questions are really questions about groups:

• Which users have the admin role?
• Which products are in my cart and on sale?
• Which students joined the class but never submitted homework?
• Which permissions does this user have?

If you can phrase your problem as "groups of things" and "how do the groups overlap", sets will make the code shorter and the thinking clearer.

2. Sets Versus Arrays

You already know arrays. How is a set different?

Use an array when the order or position matters: a playlist, the steps of a recipe, a list of search results ranked by score. Use a set when you only care about membership: a list of tags, the IDs of users who already voted, the words seen so far.

The "fast" row matters. In chapter 9 you will measure exactly how much faster, but here is the idea. With an array of a million IDs, includes may have to look at every one. A set can answer "is this ID here?" almost instantly, no matter how big it is, thanks to a trick called hashing (you will see its cousin in chapter 6).

3. JavaScript's Set

JavaScript has a built-in Set. The basics:

const tags = new Set();

tags.add("css");
tags.add("js");
tags.add("css"); // already there: nothing happens

console.log(tags.size);      // 2
console.log(tags.has("js")); // true
console.log(tags.has("go")); // false

tags.delete("js");
console.log([...tags]);      // [ 'css' ]

new Set() makes an empty set. .add() puts a value in. .has() asks the membership question. .delete() removes. .size is a property (without parentheses), unlike the array's .length, but it works the same way. The spread syntax [...tags] turns a set back into an array.

The most popular trick is removing duplicates from an array: build a set from the array, then spread it back:

const tags = ["css", "js", "css", "html", "js"];
const unique = [...new Set(tags)];

console.log(unique); // [ 'css', 'js', 'html' ]

A set compares values with the same rules as ===, with one friendly exception: NaN counts as equal to itself. That has a gotcha for objects and arrays, which are compared by identity, not by content:

console.log(new Set([1, "1"]).size);       // 2   (different types)
console.log(new Set([[1], [1]]).size);     // 2   (two different arrays)

So a set of objects is not a set of "records with the same fields". If your items are objects, store a unique key such as user.id in the set instead.

4. Thinking in Venn Diagrams

A Venn diagram draws each set as a circle. Where circles overlap are the items that belong to both. You have probably seen one in school. It is still the best tool for set problems, so draw one on paper whenever a question has the words "and", "or", "but not", or "only".

Take two sets of people:

Signed up: Dara, Sokha, Vanna, Bopha
Paid:      Sokha, Bopha, Chantha

Draw two overlapping circles. Sokha and Bopha go in the overlap, because they are in both. Dara and Vanna go in the "signed up" circle only. Chantha goes in the "paid" circle only (maybe a walk-in who paid at the door).

Every question you can ask is a way of shading part of that picture. The next section gives each shading a name.

5. Union, Intersection, Difference

Let A be the set signed up and B the set paid. The three core operations are:

Notice how similar they feel to the previous chapter. Union is OR, intersection is AND, and difference is "A AND NOT B". Boolean logic applied to groups.

Difference is not symmetric. A \ B (signed up but did not pay) is a different group from B \ A (paid but never signed up): Dara and Vanna versus Chantha.

JavaScript's Set does not give you these as methods on older runtimes, but they take one line each. Using the spread operator and filter:

const signedUp = new Set(["Dara", "Sokha", "Vanna", "Bopha"]);
const paid = new Set(["Sokha", "Bopha", "Chantha"]);

const union = new Set([...signedUp, ...paid]);
const both = new Set([...signedUp].filter((name) => paid.has(name)));
const unpaid = new Set([...signedUp].filter((name) => !paid.has(name)));

console.log(union); // Set(5) { 'Dara', 'Sokha', 'Vanna', 'Bopha', 'Chantha' }
console.log(both);  // Set(2) { 'Sokha', 'Bopha' }
console.log(unpaid); // Set(2) { 'Dara', 'Vanna' }

Read the unpaid line aloud: "take everyone who signed up, keep those that paid does not have". It is the exact sentence you would say to a colleague.

There is also a handy counting rule. The size of a union equals the sizes of the two sets added together, minus the overlap, because the overlap was counted twice:

console.log(union.size);                           // 5
console.log(signedUp.size + paid.size - both.size); // 5  (4 + 3 - 2)

Newer JavaScript: recent runtimes (Node 22 and current browsers) include built-in union(), intersection(), difference(), symmetricDifference(), and isSubsetOf() methods on Set. We write our own in this series so it works everywhere and so you see what they do inside.

6. Subsets and Symmetric Difference

Two more ideas complete the toolbox.

A set A is a subset of B (A ⊆ B) when every item of A is also in B. It answers "does B cover everything A needs?" For example, a user has the permissions {read, write}. An action needs {read}. Is the needed set a subset of what the user has? Yes, so the action is allowed. A different action needs {read, delete}. That is not a subset, because delete is missing.

function isSubset(a, b) {
  return [...a].every((item) => b.has(item));
}

const has = new Set(["read", "write"]);

console.log(isSubset(new Set(["read"]), has));           // true
console.log(isSubset(new Set(["read", "delete"]), has)); // false
console.log(isSubset(new Set(), has));                   // true

The last line surprises people: the empty set is a subset of every set. Think of it as "an action that needs no permissions is always allowed". This is the same logic as [].every(...) always returning true, which you saw in the array methods.

The symmetric difference is "in one set or the other, but not in both". It is the set version of XOR from Boolean Logic. To find what changed between yesterday's list and today's, it gives you everyone who joined or left. You can build it from the pieces you already have: (A \ B) ∪ (B \ A).

// signedUp and paid from the last section
const odd = new Set([
  ...[...signedUp].filter((x) => !paid.has(x)),
  ...[...paid].filter((x) => !signedUp.has(x)),
]);

console.log(odd); // Set(3) { 'Dara', 'Vanna', 'Chantha' }

Two sets are equal when each is a subset of the other. Order does not matter.

7. Real Questions, Real Sets

Here is how typical product questions turn into set operations:

A small example. A marketing team wants to email everyone who opened the newsletter but has not yet bought a ticket:

const opened = new Set([101, 102, 103, 104, 105]);
const bought = new Set([102, 105, 200]);

const toEmail = [...opened].filter((id) => !bought.has(id));

console.log(toEmail); // [ 101, 103, 104 ]

Notice the pattern: loop over the smaller or more relevant set, and test membership in the other with .has(). Because .has() is fast, this scales to millions of IDs. The same job done with opened.filter((id) => !boughtArray.includes(id)) would be far slower when boughtArray is huge.

Another everyday set: deduplicating while keeping first-seen order, since a Set remembers the order items were added:

const visits = ["/", "/blog", "/", "/cohort", "/blog"];

console.log([...new Set(visits)]); // [ '/', '/blog', '/cohort' ]

8. Sets, Bit Flags, and SQL

Two connections will make later chapters easier.

Bit flags are sets. In chapter 3 a single number stored the permissions READ = 1, WRITE = 2, EXEC = 4. That number is a set, packed into bits, and the bitwise operators are the set operations:

const READ = 1, WRITE = 2, EXEC = 4;

const a = READ | WRITE; // 3: {read, write}
const b = WRITE | EXEC; // 6: {write, exec}

console.log(a | b);  // 7  (read, write, exec)
console.log(a & b);  // 2  (write only)
console.log(a & ~b); // 1  (read only)
console.log(a ^ b);  // 5  (read and exec)

The bitmask version is tiny and extremely fast, but it only works when the possible items are a small, fixed list (up to 31 flags in a normal JavaScript integer). A Set works for any values, like names or IDs. Pick the tool that matches the problem.

SQL joins are set operations too. If you have used a database, an INNER JOIN keeps rows that match on both sides, which is an intersection. A LEFT JOIN ... WHERE right.id IS NULL keeps rows from the left that have no partner on the right, which is a difference. UNION in SQL is literally union. Thinking in Venn diagrams helps you choose the right join before you write it.

9. Recipe: sets.js for mathlab

Add the set helpers to mathlab. Create src/sets.js:

// Every function takes two Sets and returns a NEW Set.
export function union(a, b) {
  return new Set([...a, ...b]);
}

export function intersection(a, b) {
  return new Set([...a].filter((x) => b.has(x)));
}

export function difference(a, b) {
  return new Set([...a].filter((x) => !b.has(x)));
}

export function symmetricDifference(a, b) {
  return union(difference(a, b), difference(b, a));
}

export function isSubset(a, b) {
  return [...a].every((x) => b.has(x));
}

None of these change their inputs. They build and return a new set, which keeps them safe to call from anywhere. symmetricDifference reuses the two functions above it, so it needs no new logic.

Add it to src/index.js:

export * from "./sets.js";

Now try it in demo.js:

import {
  union,
  intersection,
  difference,
  symmetricDifference,
  isSubset,
} from "./src/sets.js";

const signedUp = new Set(["Dara", "Sokha", "Vanna", "Bopha"]);
const paid = new Set(["Sokha", "Bopha", "Chantha"]);

console.log(union(signedUp, paid));
console.log(intersection(signedUp, paid));
console.log(difference(signedUp, paid));
console.log(symmetricDifference(signedUp, paid));
console.log(isSubset(new Set(["Sokha"]), signedUp));
console.log(isSubset(paid, signedUp));

Run it:

node demo.js

Set(5) { 'Dara', 'Sokha', 'Vanna', 'Bopha', 'Chantha' }
Set(2) { 'Sokha', 'Bopha' }
Set(2) { 'Dara', 'Vanna' }
Set(3) { 'Dara', 'Vanna', 'Chantha' }
true
false

The last line is false because Chantha paid without signing up, so paid is not covered by signedUp.

10. Try It Yourself

1. Remove duplicates. Write unique(array) that returns an array without duplicates, in first-seen order. Test it with [3, 1, 3, 2, 1].
2. Two-set questions. Using courseA = {"Dara", "Sokha", "Vanna"} and courseB = {"Vanna", "Bopha"}, find who takes both courses, who takes at least one, and who takes only course A.
3. Equal sets. Write isEqual(a, b) using isSubset twice. Check that {1, 2} equals {2, 1} and that {1, 2} does not equal {1, 2, 3}.
4. Bitmask twin. Number five people 0 to 4 and store each group as a bitmask, where person id is the bit 1 << id. Make a signedUp mask and a paid mask, compute "signed up but not paid" with & and ~, then loop over the bits to list who is in the result.
5. Permission check. Write canDo(userPermissions, required) that returns true only when all required permissions are present. Use isSubset and test it with an empty required set.
6. Think harder. How would you find the items that appear in all three of three sets? Hint: apply intersection twice.

Sets answer "who is in which group". Next we look at numbers that live in a loop, such as the hands of a clock or the slides of a carousel: Modular Arithmetic explains %, the negative-number trap, and how check digits catch typos in card numbers.