20: - A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 - Jay Wengrow - RutLib.com

Chapter 20

These are the solutions to the exercises found in the section .

We can optimize this algorithm if we ask ourselves, “If I could magically find a desired piece of information in O(1) time, can I make my algorithm faster?”

Specifically, as we iterate over one array, we’d want to “magically” look up that athlete from the other array in O(1) time. To accomplish this, we can first transform one of the arrays into a hash table. We’ll use the full name (that is, the first and last name) as the key, and True (or any arbitrary item) as the value.

Once we’ve turned one array into this hash table, we then iterate over the other array. As we encounter each athlete, we do an O(1) lookup in the hash table to see if that athlete already plays the other sport. If they do, we add that athlete to our multisport_athletes array, which we return at the end of the function.

Here’s the code for this approach:

	def find_multisport_athletes(array_1, array_2):
	hash_table = {}
	multisport_athletes = []

	for athlete in array_1:
	hash_table[athlete["first_name"]
	+ " "
	+ athlete["last_name"]] = True

	for athlete in array_2:
	if hash_table.get(athlete["first_name"]
	+ " "
	+ athlete["last_name"]):
	multisport_athletes.append(athlete["first_name"]
	+ " "
	+ athlete["last_name"])

	return multisport_athletes

This algorithm is O(N + M) since we iterate through each set of players just once.

For this algorithm, generating examples to find a pattern will be immensely helpful.

Let’s take an array that has six integers and see what would happen if we removed a different integer each time:

	[1, 2, 3, 4, 5, 6] : missing 0: sum = 21
	[0, 2, 3, 4, 5, 6] : missing 1: sum = 20
	[0, 1, 3, 4, 5, 6] : missing 2: sum = 19
	[0, 1, 2, 4, 5, 6] : missing 3: sum = 18
	[0, 1, 2, 3, 5, 6] : missing 4: sum = 17
	[0, 1, 2, 3, 4, 6] : missing 5: sum = 16

Hmm. When we remove the 0, the sum is 21. When we remove the 1, the sum is 20. And when we remove the 2, the sum is 19, and so on. This definitely seems like a pattern!

Before we go further, let’s call the 21 in this case the “full sum.” This is the sum of the array when it’s just missing the 0.

If we analyze these cases carefully, we’ll see that the sum of any array is less than the full sum by the amount of the missing number. For example, when we’re missing the 4, the sum is 17, which is four less than 21. And when we’re missing the 1, the sum is 20, which is one less than 21.

So we can begin our algorithm by calculating what the full sum is. We can then subtract the actual sum from the full sum, and that will be our missing number.

Here’s the code for this:

	def find_missing_number(array):
	full_sum = 0

	for num in range(1, len(array) + 1):
	full_sum += num

	current_sum = 0

	for num in array:
	current_sum += num

	return full_sum - current_sum

This algorithm is O(N). It takes N steps to calculate the full sum and then another N steps to calculate the actual sum. This is 2N steps, which reduces to O(N).

We can make this function much faster if we use a greedy algorithm. (Perhaps this shouldn’t be a surprise given that our code is trying to make the greatest possible profit on stocks.)

To make the most profit, we want to buy as low as possible and sell as high as possible. Our greedy algorithm begins by assigning the very first price to be the buy_price. We then iterate over all the prices, and as soon as we find a lower price, we make it the new buy_price.

Similarly, as we iterate over the prices, we check how much profit we’d make if we sold at that price. This is calculated by subtracting the buy_price from the current price. In good greedy fashion, we save this profit in a variable called greatest_profit. As we iterate through all the prices, whenever we find a greater profit, we turn that into the greatest_profit.

By the time we’re done looping through the prices, the greatest_profit will hold the greatest possible profit we can make by buying and selling the stock one time.

Here’s the code for our algorithm:

	def find_greatest_profit(array):
	buy_price = array[0]
	greatest_profit = 0

	for price in array:
	potential_profit = price - buy_price

	if price < buy_price:
	buy_price = price
	elif potential_profit > greatest_profit:
	greatest_profit = potential_profit

	return greatest_profit

Because we iterate over the N prices just once, our function takes O(N) time. We not only made a lot of money, but we made it fast.

This is another algorithm where generating examples to find a pattern will be the key to optimizing it.

As stated in the exercise, it’s possible for the greatest product to be a result of negative numbers. Let’s look at various examples of arrays and their greatest products formed by two numbers:

	[-5, -4, -3, 0, 3, 4] -> Greatest product: 20 (-5 * -4)
	[-9, -2, -1, 2, 3, 7] -> Greatest product: 21 (3 * 7)
	[-7, -4, -3, 0, 4, 6] -> Greatest product: 28 (-7 * -4)
	[-6, -5, -1, 2, 3, 9] -> Greatest product: 30 (-6 * -5)
	[-9, -4, -3, 0, 6, 7] -> Greatest product: 42 (6 * 7)

Seeing all these cases may help us realize that the greatest product can only be formed by either the greatest two numbers or the lowest two (negative) numbers.

With this in mind, we should design our algorithm to keep track of these four numbers:

The greatest number
The second-to-greatest number
The lowest number
The second-to-lowest number

We can then compare the product of the two greatest numbers versus the product of the two lowest numbers. And whichever product is greater is the greatest product in the array.

Now, how do we find the greatest two numbers and the lowest two numbers? If we sorted the array, that would be easy. But that’s still O(N log N), and the instructions say that we can achieve O(N).

In fact, we can find all four numbers in a single pass through the array. It’s time to get greedy again.

Here’s the code, followed by its explanation:

	def greatest_product(array):
	greatest_number = float("-inf")
	second_to_greatest_number = float("-inf")

	lowest_number = float("inf")
	second_to_lowest_number = float("inf")

	for number in array:
	if number >= greatest_number:
	second_to_greatest_number = greatest_number
	greatest_number = number
	elif number > second_to_greatest_number:
	second_to_greatest_number = number

	if number <= lowest_number:
	second_to_lowest_number = lowest_number
	lowest_number = number
	elif number < second_to_lowest_number:
	second_to_lowest_number = number

	greatest_product_from_two_highest = (greatest_number
	* second_to_greatest_number)

	greatest_product_from_two_lowest = (lowest_number
	* second_to_lowest_number)

	if (greatest_product_from_two_highest
	> greatest_product_from_two_lowest):
	return greatest_product_from_two_highest
	else:
	return greatest_product_from_two_lowest

Before we begin our loop, we set the greatest_number and second_to_greatest_number to be negative infinity. This ensures they start out lower than any number currently in the array.

We then iterate over each number. If the current number is greater than the greatest_number, we greedily turn the current number into the new greatest_number. If we’ve already found a second_to_greatest_number, we reassign the second_to_greatest_number to be whatever the greatest_number was before we reached the current number. This ensures the second_to_greatest_number will indeed be the second-to-greatest number.

If the current number we’re iterating over is less than the greatest_number but greater than the second_to_greatest_number, we update the second_to_greatest_number to be the current number.

We follow this same process to find the lowest_number and the second_to_lowest_number.

Once we’ve found all four numbers, we compute the products from the two highest numbers and the products of the two lowest numbers and return whichever product is greater.

The key to optimizing this algorithm is the fact that we’re sorting a finite number of values. Specifically, there are only eleven types of temperature readings that we may find in this array, namely:

95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105

Let’s assume our input array is:

[98, 99, 95, 105, 104, 99, 101, 99, 101, 97]

If we imagine our array of temperatures as a hash table, we can store each temperature as a key and the number of occurrences as the value. This would look something like this:

{98: 1, 99: 3, 95: 1, 105: 1, 104: 1, 101: 2, 97:1}

With this in mind, we can run a loop that runs from 95 up through 105 and checks the hash table for how many occurrences of that temperature there are. Each of these lookups take just O(1) time.

Then we use that number of occurrences to populate a new array. Because our loop is set to go up from 95 through 105, our array will end up in perfect ascending order.

Here’s the code for this:

	def sort_temperatures(array):
	hash_table = {}

	for temperature in array:
	if temperature in hash_table:
	hash_table[temperature] += 1
	else:
	hash_table[temperature] = 1

	sorted_temperatures = []
	temperature = 95

	while temperature <= 105:
	if temperature in hash_table:
	for i in range(hash_table[temperature]):
	sorted_temperatures.append(temperature)

	temperature += 1

	return sorted_temperatures

Let’s now analyze the efficiency of this algorithm. We take N steps to create the hash table. We then run a loop eleven times for all possible temperatures from 95 up to 105.

In each round of this loop, we run a nested loop to populate the sorted_temperatures with the temperatures. However, this inner loop will never end up running more times than the N temperatures from the input array. This is because the inner loop only runs one time for each temperature in the original array.

Thus, we have N steps to create the hash table, eleven steps for the outer loop, and N steps for the inner loop. This is 2N + 11, which is reduced to a beautiful O(N).

This algorithm is a classic sorting algorithm called counting sort. It’s useful any time we’re dealing with a relatively small range of possible input values, such as our case where there are only eleven possible values.

This optimization employs the most brilliant use of magical lookups that I’ve ever seen.

Imagine we’re iterating over the array of numbers and we encounter a 5. Let’s ask ourselves the magical lookup question: “If I could magically find a desired piece of information in O(1) time, can I make my algorithm faster?”

Well, to determine whether the 5 is part of the longest consecutive sequence, we’d want to know whether there’s a 6 in the array. We’d also want to know if there’s a 7, and an 8, and so on.

We can achieve each of those lookups in O(1) time if we first store all the numbers from our array in a hash table; that is, the array [10, 5, 12, 3, 55, 30, 4, 11, 2] could look like this if we moved the data to a hash table:

	{10: True, 5: True, 12: True, 3: True, 55: True,
	30: True, 4: True, 11: True, 2: True}

In this case, if we encounter the 2, we can then run a loop that keeps checking for the next number in the hash table. If it finds it, we increase the length of the current sequence by one. The loop repeats this process until it can’t find the next number in the sequence. Each of these lookups takes just one step.

But, you may ask, how does this help? Imagine our array is [6, 5, 4, 3, 2, 1]. When we iterate over the 6, we’ll find that there isn’t a sequence that builds up from there. When we reach the 5, we’ll find the sequence 5-6. When we reach the 4, we’ll find the sequence 4-5-6. When we reach the 3, we’ll find the sequence 3-4-5-6, and so on. We’ll still end up going through about N² / 2 steps finding all those sequences.

The answer is that we’ll only start building a sequence if the current number is the bottom number of the sequence. So we won’t build 4-5-6 when there’s a 3 in the array.

But how do we know if the current number is the bottom of a sequence? By doing a magical lookup!

How? Before running a loop to find a sequence, we’ll do an O(1) lookup of the hash table to check whether there’s a number that’s 1 less than current number. So if the current number is 4, we’ll first check to see whether there’s a 3 in the array. If there is, we won’t bother to build a sequence. We only want to build a sequence starting from the bottom number of that sequence; otherwise we have redundant steps.

Here’s the code for this:

	def longest_sequence_length(array):
	hash_table = {}
	greatest_sequence_length = 0

	for number in array:
	hash_table[number] = True

	for number in array:
	if not hash_table.get(number - 1):
	current_sequence_length = 1
	current_number = number

	while hash_table.get(current_number + 1):
	current_number += 1
	current_sequence_length += 1

	if current_sequence_length > greatest_sequence_length:
	greatest_sequence_length = current_sequence_length

	return greatest_sequence_length

In this algorithm, we take N steps to build the hash table. We take another N steps to iterate through the array. And we take about another N steps looking up numbers in the hash table to build the different sequences. All in all, this is about 3N, which is reduced to O(N).

Thank you!

We hope you enjoyed this book and that you’re already thinking about what you want to learn next. To help make that decision easier, we’re offering you this gift.

Head on over to right now, and use the coupon code BUYANOTHER2023 to save 30% on your next ebook. Offer is void where prohibited or restricted. This offer does not apply to any edition of the The Pragmatic Programmer ebook.

And if you’d like to share your own expertise with the world, why not propose a writing idea to us? After all, many of our best authors started off as our readers, just like you. With up to a 50% royalty, world-class editorial services, and a name you trust, there’s nothing to lose. Visit today to learn more and to get started.

We thank you for your continued support, and we hope to hear from you again soon!

The Pragmatic Bookshelf