Modern JavaScript: Set Operations

Welcome to the Set Operations lesson!

This lesson is shown as static text below. However, it's designed to be used interactively. Click the button below to start!

Most programming languages provide the three most common operations: union, intersection, and difference. These operations have been added to JavaScript, but they're not widely-supported yet.
It's OK if these operations aren't familiar. In this lesson we'll define and implement them ourselves.
First: we sometimes want to find a set union, which is every element that's in either set1 or set2. The closest array equivalent is concat, which merges two or more arrays:

const array1 = [1, 2, 3];
const array2 = [2, 3, 4];
array1.concat(array2);

Result:

Set union is the same thing, but it respects the constraint that a set only contains unique values. If the concat operation above were a set union, we'd expect a result of [1, 2, 3, 4].
Fortunately, implementing set union is easy by using some tricks. One trick is that we can pass an array to the new Set constructor to build a set with all of the elements from the array, just as we did before. Another trick is that we can use the spread operator, ..., to build arrays that contain the elements from a set, or even from multiple sets: [...set1, ...set2].
(Under the hood, sets are JavaScript iterators, and the new Set constructor accepts iterators as arguments. Iterators are covered elsewhere in this course and aren't necessary to understand this lesson.)
By combining those two tricks, we can build a true set union:

const set1 = new Set([1, 2, 3]);
const set2 = new Set([2, 3, 4]);
const unionSet = new Set([...set1, ...set2]);
[unionSet.has(1), unionSet.has(4)];

Result:

[true, true]

Remember, when we create a set from an array with duplicate values, the duplicates are removed.
Note: this code example reuses elements (variables, etc.) defined in earlier examples.
>
Array.from(unionSet);
Result:
[1, 2, 3, 4]
Here's a code problem:
Implement a general-purpose setUnion function that returns the union of two sets.
function setUnion(set1, set2) {
return new Set([...set1, ...set2]);
}
const union = setUnion(
new Set([1, 2, 3]),
new Set([2, 3, 4])
);
[union.has(1), union.has(2), union.has(3), union.has(4)];
Goal:
[true, true, true, true]
Yours:
[true, true, true, true]
Show Author's Answer
Second: we sometimes want to find a set intersection, which is every element that's in both set1 and set2. With arrays, we can use filter to do that. (filter takes a function f, calls it on every array element, and returns an array with all of the elements where f(element) is true.)
In English, the next code example can be read as "build an array of all array1 elements where array2 also includes that element."

const array1 = [1, 2, 3];
const array2 = [2, 3, 4];
array1.filter(n => array2.includes(n));

Result:

[2, 3]

For sets, we can use the same trick. We'll convert set1 into an array, then filter it, checking for whether each element exists in set2.

const set1 = new Set([1, 2, 3]);
const set2 = new Set([2, 3, 4]);
const intersectionSet = new Set(
  Array.from(set1).filter(n => set2.has(n))
);
[intersectionSet.has(2), intersectionSet.has(4)];

Result:

[true, false]

Note: this code example reuses elements (variables, etc.) defined in earlier examples.
>
Array.from(intersectionSet);
Result:
[2, 3]
Here's a code problem:
Implement a general-purpose setIntersection function that returns the intersection of two sets.
function setIntersection(set1, set2) {
return new Set(Array.from(set1).filter(n => set2.has(n)));
}
const intersection = setIntersection(
new Set([1, 2, 3]),
new Set([2, 3, 4])
);
[
intersection.has(1),
intersection.has(2),
intersection.has(3),
intersection.has(4)
];
Goal:
[false, true, true, false]
Yours:
[false, true, true, false]
Show Author's Answer
Sometimes we want to find every element in set1 that isn't also in set2. For example:
- set1 = new Set([1, 2, 3])
- set2 = new Set([2, 3, 4])
- The element 1 is in set1 but not set2, so the set difference is [1].
The code for set difference is exactly like intersection, but we put a ! inside the filter. Then we use filter to build an array of all set1 elements that aren't included in set2.

const set1 = new Set([1, 2, 3]);
const set2 = new Set([2, 3, 4]);
const differenceSet = new Set(
  Array.from(set1).filter(n => !set2.has(n))
);
[differenceSet.has(1), differenceSet.has(2)];

Result:

[true, false]

Note: this code example reuses elements (variables, etc.) defined in earlier examples.
>
Array.from(differenceSet);
Result:
[1]
In the examples above, the element 4 is in the second set, but not in the first set. When speaking casually, we might say that 4 is part of the "difference" between the two sets. But in both math and programming, elements from the second set aren't included in the set difference.
(There's also a related operation called "symmetric set difference". It means "every element that's in only one of the two sets." If we used symmetric set difference in the example above, we'd get [1, 4]. But we won't mention symmetric set difference again in this lesson.)
Here's a code problem:
Implement a general-purpose setDifference function that returns the difference of two sets. Remember that "set difference" means "all items that are in the first set, but aren't in the second set."
function setDifference(set1, set2) {
return new Set(Array.from(set1).filter(n => !set2.has(n)));
}
const difference = setDifference(
new Set([1, 2, 3]),
new Set([2, 3, 4])
);
[
difference.has(1),
difference.has(2),
difference.has(3),
difference.has(4)
];
Goal:
[true, false, false, false]
Yours:
[true, false, false, false]
Show Author's Answer
Set union is different from array concatenation because it results in a set, which has no duplicates. Set intersection and difference both do the same things as the array versions. But they're better than the array versions because they're much faster. As before, we take advantage of .has to quickly look up elements in the set without looping through every element.
(Using the technical terminology: all of the set operations implemented here are O(n) because they loop over elements in one array, but the array equivalents are O(n^2) because they use a nested loop to look up elements in two arrays.)
It's good to know about these set operations, even if you don't memorize exactly how to write them! Most uses of sets will require one or more of these functions.