Sets

This chapter focuses on working with sets. The concepts of sets from both a mathematical definition and on the implementation level are described and explored. Common set operations, as well as their implementations, are covered in great detail. By end of this chapter, you will understand how to use JavaScript’s native Set object to utilize set operations.

Introducing Sets

Sets are one of the most fundamental data structures. The idea of a set is simple: it is a group of definite, distinct objects. In layman’s terms, in programming, a set is a group of unordered unique (no duplicate) elements. For example, a set of integers may be {1, 2, 3, 4}. Within this, its subsets are {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Sets are important for checking and adding a unique element in O(1) constant time. The reason that sets have constant time operations is that the implementations are based on that of hash tables (covered in Chapter 11).

Set is natively supported in JavaScript as follows:

1 var exampleSet = new Set();

The native Set object has only one property: size (integer). This property is the current number of elements within the set.

Set Operations

The set is a powerful data structure for performing uniqueness checks. This section will cover the following key operations: insertion, deletion, and contains.

Insertion

Set has one primary function: to check for uniqueness. Set can add items, but duplicates are not allowed.

1 var exampleSet = new Set();

2 exampleSet.add(1); // exampleSet: Set {1}

3 exampleSet.add(1); // exampleSet: Set {1}

4 exampleSet.add(2); // exampleSet: Set {1, 2}

Notice that adding the duplicate element does not work for a set. As discussed in the introduction, insertion into a set occurs in constant time.

Time Complexity: O(1)

Deletion

Set can also delete items from the set. Set.delete returns a boolean (true if that element exists and was deleted, false otherwise).

1 var exampleSet = new Set();

2 exampleSet.add(1); // exampleSet: Set {1}

3 exampleSet.delete(1); // true

4 exampleSet.add(2); // exampleSet: Set {2}

This is useful for being able to delete items in constant time in contrast to arrays where it would take O(n) time to delete an item.

Time Complexity: O(1)

Contains

Set.has does a quick O(1) lookup to check whether the element exists within the set.

1 var exampleSet = new Set();

2 exampleSet.add(1); // exampleSet: Set {1}

3 exampleSet.has(1); // true

4 exampleSet.has(2); // false

5 exampleSet.add(2); // exampleSet: Set {1, 2}

6 exampleSet.has(2); // true

Time Complexity: O(1)

Other Utility Functions

In addition to the natively supported set functions, other essential operations are available; they are explored in this section.

Intersection

First, the intersection of two sets consists of the common elements between those two sets. This function returns a set with common elements between two sets:

1 function intersectSets (setA, setB) {

2 var intersection = new Set();

3 for (var elem of setB) {

4 if (setA.has(elem)) {

5 intersection.add(elem);

6 }

7 }

8 return intersection;

9 }

10 var setA = new Set([1, 2, 3, 4]),

11 setB = new Set([2, 3]);

12 intersectSets(setA,setB); // Set {2, 3}

isSuperSet

Second, a set is a “superset” of another set if it contains all the elements of the other set. This function checks whether a set is a superset of another. This is implemented simply by checking whether the other set contains all the elements of the reference set.

1 function isSuperset(setA, subset) {

2 for (var elem of subset) {

3 if (!setA.has(elem)) {

4 return false;

5 }

6 }

7 return true;

8 }

9 var setA = new Set([1, 2, 3, 4]),

10 setB = new Set([2, 3]),

11 setC = new Set([5]);

12 isSuperset(setA, setB); // true

13 // because setA has all elements that setB does

14 isSuperset(setA, setC); // false

15 // because setA does not contain 5 which setC contains

Union

Third, the union of two sets combines the elements from both sets. This function returns a new set with both elements without duplicates.

1 function unionSet(setA, setB) {

2 var union = new Set(setA);

3 for (var elem of setB) {

4 union.add(elem);

5 }

6 return union;

7 }

8 var setA = new Set([1, 2, 3, 4]),

9 setB = new Set([2, 3]),

10 setC = new Set([5]);

11 unionSet(setA,setB); // Set {1, 2, 3, 4}

12 unionSet(setA,setC); // Set {1, 2, 3, 4, 5}

Difference

Finally, the difference of set A from set B is all of the elements in set A that are not in set B. This function implements the difference operation by making use of the native delete method.

1 function differenceSet(setA, setB) {

2 var difference = new Set(setA);

3 for (var elem of setB) {

4 difference.delete(elem);

5 }

6 return difference;

7 }

8 var setA = new Set([1, 2, 3, 4]),

9 setB = new Set([2, 3]);

10 differenceSet(setA, setB); // Set {1, 4}

Summary

A set is a fundamental data structure to represent unordered unique elements. In this chapter, JavaScript’s native Set object was introduced. The Set object supports insertion, deletion, and contains check, which all have a time complexity of O(1). With these built-in methods, other fundamental set operations such as intersection, difference, union, and superset check are implemented. These will enable you to implement algorithms with fast uniqueness checks in future chapters.

Table 9-1 summarizes the set operations.

Table 9-1

Set Summary

Operation	Function Name	Description
Insertion	Set.add	Native JavaScript. Adds the element to the set if it’s not already in the set.
Deletion	Set.delete	Native JavaScript. Deletes the element from the set if it’s in the set.
Contains	Set.has	Native JavaScript. Checks whether an element exists within in the set.
Intersection (A∩B)	intersectSets	Returns a set with common elements of set A and set B.
Union (A∪B)	unionSet	Returns a set with all elements of set A and set B.
Difference (A-B)	differenceSet	Returns a set with all elements.

Exercises

USING SETS TO CHECK FOR DUPLICATES IN AN ARRAY

Check whether there are any duplicates in an array of integers using sets. By converting the array into a set, the size of the set can be compared with the length of the array to check for duplicates easily.

1 function checkDuplicates(arr) {

2 var mySet = new Set(arr);

3 return mySet.size < arr.length;

4 }

5 checkDuplicates([1,2,3,4,5]); // false

6 checkDuplicates([1,1,2,3,4,5]); // true

Time Complexity: O(n)

Space Complexity: O(n)

In an array of length n, this function has to iterate through the entire array in the worst case and also store all those elements in the set.

RETURNING ALL UNIQUE VALUES FROM SEPARATE ARRAYS

Given two integer arrays with some of the same values, return one array that has all the unique elements from both of the original arrays.

Using sets, unique elements can be stored easily. By concatenating two arrays and converting them to a set, only unique items are stored. Converting the set to an array results in an array with unique items only.

1 function uniqueList(arr1, arr2) {

2 var mySet = new Set(arr1.concat(arr2));

3 return Array.from(mySet);

4 }

6 uniqueList([1,1,2,2],[2,3,4,5]); // [1,2,3,4,5]

7 uniqueList([1,2],[3,4,5]); // [1,2,3,4,5]

8 uniqueList([],[2,2,3,4,5]); // [2,3,4,5]

Time Complexity: O(n + m )

Space Complexity: O(n + m)

The time and space complexity for this algorithm is O(n + m) where n is the length of arr1 and m is the length of arr2. This is because all elements inside both arrays need to be iterated through.

9. Sets

Introducing Sets

Set Operations

Insertion

Deletion

Contains

Other Utility Functions

Intersection

isSuperSet

Union

Difference

Summary

Exercises

USING SETS TO CHECK FOR DUPLICATES IN AN ARRAY

RETURNING ALL UNIQUE VALUES FROM SEPARATE ARRAYS