Sets

In Volume 1, Chapter 1, I introduced the notion of a set. A set is a collection of unique values; there are no duplicate values. There are many different applications where maintaining a set can be useful, which I demonstrate in the following sections.

Finding Duplicates

Suppose we have an array of integers in which there may or may not be duplicate values, and we need a function that will tell us whether there are any duplicates. For example, if we have the array [4, 3, 5, 1, 7, 2, 6, 8], our function will return False because no duplicate values are present. However, if the array is [1, 2, 3, 1], the function will return True because there are two instances of the integer 1.

The brute-force approach to detecting duplicates would be to use nested loops. The outer loop would iterate over each value, and for each value, we’d initiate a second loop that would scan the rest of the array to see if that value appears again within the array. Naturally, this approach has a speed of O(N²).

However, if we use a set-building algorithm (and the right data structure to serve as our set), we can get the job done in O(N) time. That is, throughout our algorithm, we’ll maintain a set of all the values we’ve ever encountered before. With this approach, we can scan all N integers once, following these steps:

We check the current integer to see if it’s a key in the set.
If it is, that means we’ve encountered this value before, which means the current value is a duplicate. So, our function returns True.
If the current value is not in the set, we insert it into the set. The set is a hash table that stores each integer as a key and True as the value. So, if our data is [4, 3, 5], our hash table will be {4: True, 3: True, 5: True}.
If we search the entire array without finding a duplicate, our function returns False.

Assuming that each value in our set can be accessed in constant time, this algorithm has a time complexity of O(N). That is, in the “worst case,” which is when there are no duplicates, we scan each of the N elements once. Although we also perform additional steps such as inspecting the set for the element and inserting the element into the set, this is 3N steps, which reduces to O(N).

Because the speed of this algorithm hinges upon having a set where each element can be accessed in constant time, we need to make a careful decision as to what data structure we’ll use to house our set.

Choosing the Right Set Data Structure

In Volume 1, Chapter 1, I talked about using an array to serve as a set. An array would not be ideal for our scenario of duplicate checking, since we’d have to perform a linear search on the array each time we look up a value. This means that accessing our set has a cost of O(N) time, and we’re seeking to achieve O(1) lookup time.

We’d do much better with a hash table, which offers O(1) lookups. That is, we’ll store our integers in the hash table as keys and use any arbitrary truthy value, such as True, as the hash table values. Indeed, hash tables are often used to represent sets, especially where the situation warrants many lookups.

With this in mind, here’s the code for detecting duplicate values where we use a hash table set:

	def has_duplicates(array):
	set = {}

	for item in array:
	if set.get(item):
	return True
	else:
	set[item] = True

	return False

This code takes O(N) time, as we iterate over each of the N array items once. This may not be earth-shattering; we wrote this same code back in Volume 1, Chapter 19. However, I’m leading up to an important point, so bear with me.

In any case, this was one simple application where maintaining a set was useful. Let’s look at one more.

Counting Sort

As I’ve mentioned numerous times, the fastest sorting algorithms take O(N log N) time for average-case scenarios. However, this isn’t quite true for every application. We can sort certain data sets, believe it or not, in considerably faster time.

Suppose we have an array of integers and we have some special knowledge about the nature of these integers. For example, we may know that all of these integers fall within the range of 0 to 9999 and that there are no duplicates.

Armed with this knowledge about our data, we can use a set to help us sort the integers in linear time. Here’s how:

We create a new empty array that will eventually contain all the sorted integers. (Alternatively, we could have chosen to overwrite the original array; it’s easier to explain the algorithm this way.)
We scan all the integers and build a set—using a hash table—that stores each integer as a key and True as the value. So, if our data is [860, 2345, 9999], our hash table will be {860: True, 2345: True, 9999: True}.
We then start a loop that I’ll call the “counting phase.” The loop will run 10,000 times, keeping track of a variable called number, which, before the loop begins, starts out as 0. In each round of the loop, we increment number by 1. In the loop’s final iteration, number will be 9999.
In each iteration, we look up number inside our hash table. If it is there, this means that number is also in the original array. As such, we append number to the end of our new array.

And that’s it! In other words, we only need to execute two simple loops. The first loop takes all of our integers and inserts them into a hash table. The second loop then counts from 0 to 9999—that is, the variable number—and checks to see if number is inside the hash table. (If it is, we append number to our result array.) The reason this effectively sorts our array is that because we’re counting number from 0 to 9999 in sorted order, our final result array will also be in sorted order.

This algorithm, which many computer scientists call counting sort, doesn’t have to compare any of the values we’re sorting to each other, which is what slows all the other sorting algorithms down. Here’s the code for counting sort:

	def counting_sort(array):
	sorted_array = []
	set = {}

	for value in array:
	set[value] = True

	for number in range(10000):
	if set.get(number):
	sorted_array.append(number)

	return sorted_array

As you can see, we use a hash table to serve as our set. Again, this allows us to look up each integer in constant time.

The Time Complexity of Counting Sort

The counting sort algorithm first inserts all N integers of the array into the hash table. It then performs a fixed number of 10,000 steps, looking up the numbers 1 through 10000 in the hash table. If, say, we had 5,000 integers that lie in the range of 1 through 10000, the algorithm would perform a total of 15,000 steps. That is, it inserts the 5,000 integers and then performs 10,000 hash table lookups.

To generalize counting sort’s time complexity in terms of Big O, we can use the variable N to refer to the number of integers in the array, and the variable R to refer to the size of the range of data. (In our current example, N is 5,000, and R is 10,000.) Armed with these variables, we’d say that counting sort has a speed of O(N+R).

Had we gone with Quicksort or Mergesort, though, sorting would have taken, on average, 65,000 steps. That is, these algorithms take O(N log N) time. In this example, N is 5,000, and log N is 13, so 5000 * 13 = 65000.

This serves as another example of how sets, assuming they have O(1) lookups, can significantly speed up our code.

Before moving on, it is important to remember that counting sort isn’t always the best choice. If, for example, our integers could lie in the range of 1 to 1,000,000, counting sort would end up taking at least 1,005,000 steps. Because we only have 5,000 values in our array, Quicksort would still have taken 65,000 steps. So, make sure that counting sort is a good fit for your data set before blindly using it. The shorter the range, the better fit that counting sort may be.

It’s also worth noting that counting sort can also work even if our array contains duplicate values. That is, instead of setting each hash table value simply to True, we’d instead set it to be an integer representing the tally of how many times we encounter that value. That is, the first time we encounter a particular integer, we set its hash table value to 1. When we encounter it a second time, we increment the corresponding hash table value to 2, and so on. So, if the data was [7, 1, 1, 1, 4, 4], our hash table would end up being:

{7: 1, 1: 3, 4: 2}

When we get to the number 4 during the counting phase, we’ll add two 4’s to our result array because the hash table tells us that there are two of them.

Later, I’ll make an important distinction between counting sort, where the data contains duplicates, vs. where it does not. For now, though, keep in mind that counting sort can work for both scenarios.