Change the Data Structure

Another helpful optimization technique is to imagine what would happen if we stored our given data in an alternative data structure.

For example, we may be working on a problem where the data is given to us in the form of an array. However, reimagining that same data stored as a hash table, tree, or other data structure can sometimes reveal clever optimization opportunities.

Our use of a hash table for the magical lookup technique earlier is a specific example of this. And we’re about to see that changing the data structure can be useful for other scenarios as well.

The Anagram Checker

Here’s one example. Let’s say we’re writing a function that determines whether two given strings are anagrams of one another. We encountered an anagram function before in , but there we dealt with a function that produced every anagram of a string. Here, we’re just going to compare two strings side by side. We’ll return True if they’re anagrams of each other and False if they’re not.

Now, we could use the anagram-generating function to solve this problem; that is, we can produce all the anagrams of the first string and see if the second string matches any of those anagrams. However, since for N characters in the string there will always be N! anagrams, our algorithm will take at least O(N!) time. This is disastrously slow.

You know the drill. Before we proceed to optimize our code, we need to come up with our best-imaginable Big O.

Now, we certainly need to visit each character from both strings at least once. And since the input strings may be of different sizes, touching each character just once would be O(N + M). As I couldn’t imagine a faster speed for the task at hand, this is what we’ll aim for.

In theory, we could put some code at the beginning of the function that immediately returns False if the two strings have different sizes, since it’s impossible for strings of different sizes to be anagrams. In that case, the speed we’d aim for is 2N since the algorithm will only be working with strings that are the same size. This reduces to O(N).

However, for the sake of this discussion, we’ll allow someone to input two strings that may be of different sizes, and so we’ll aim for O(N + M).

Let’s work our way there.

A second possible approach to our problem is to run nested loops to compare the two strings. Specifically, as an outer loop iterates over each character from the first string, we compare that character to every character of the second string. Each time we find a match, we delete a character from the second string. The idea here is that if every character from the first string is also present in the second string, we’d end up deleting every character from the second string by the time we complete our outer loop.

So, if by the time we finish looping, characters still remain from the second string, it means the strings aren’t anagrams. Also, if we’re still iterating over the first word, but we’ve already deleted the entire second string, it also means the strings aren’t anagrams. But if we make it to the end of the loop and the second string has been completely deleted, we can conclude that the two strings are indeed anagrams.

Here’s a Python implementation of this:

Now, it just so happens that deleting items from an array while you’re looping through it can be error prone; if you don’t do it right, it’s like sawing off the tree branch you’re sitting on. But even though we’ve handled that correctly, our algorithm runs at O(N * M). This is way faster than O(N!) but much slower than the O(N + M) we’re shooting for.

An even faster approach would be to sort the two strings. If after sorting the two strings they’re exactly the same, it means they’re anagrams; otherwise, they’re not.

This approach will take O(N log N) for each string using a fast sorting algorithm like Quicksort. Since we may have two strings of different sizes, this adds up to be O(N log N + M log M). This is a nice improvement over O(N * M), but let’s not stop now—we’re aiming for O(N + M), remember?

This is where using an alternative data structure can be extremely helpful. We’re dealing with strings, but let’s imagine that we’d store the string data in other types of data structures.

We could store a string as an array of single characters. But this doesn’t help us.

Let’s next imagine the string as a hash table. What would that even look like?

One possibility is to create a hash table where each character is a key, and the value is the number of occurrences of that character within the word. For example, the string "balloon" would look like so:

This hash table indicates that the string has one "b", one "a", two "l"s, two "o"s, and one "n".

Now, this doesn’t tell us everything about the string. Namely, we couldn’t tell from the hash table the order of characters within the string. So there’s a bit of data loss in this regard.

However, that data loss is exactly what we need to help us determine whether the two strings are anagrams: two strings turn out to be anagrams if they have the same number of each character, no matter what the order is.

Take the words “rattles”, “startle”, and “starlet”. They all have two “t”s, one “a”, one “l”, one “e”, and one “s”—and that’s what allows them to be anagrams and easily reordered to become each other.

We can now write an algorithm that converts each string into a hash table that tallies the count of each type of character. Once we’ve converted the two strings into two hash tables, all that’s left is to compare the two hash tables. If they’re equal, it means the two strings are anagrams.

Here’s an implementation:

In this algorithm, we iterate over each character from both strings just once, which is N + M steps.

When checking whether the hash tables are equal with return first_word_hash_table == second_word_hash_table, Python under the hood probably takes up to another N + M steps. This is because Python has to iterate over each of the key-value pairs in the hash tables to make sure the pairs exist in both hash tables. However, this still totals just 2(N + M) steps, which reduces to O(N + M). This is much faster than any of our previous approaches.

To be fair, we’re taking up some extra space with the creation of these hash tables. Our previous suggestion of sorting the two strings and comparing them would take up no extra space if we did the sorting in place. But if speed is what we’re after, we can’t beat the hash table approach, as we touch each character from the strings just once.

By converting the strings into another data structure (in this case, hash tables), we were able to access the original data in such a way that allowed our algorithm to become blazing fast.

It’s not always obvious what new data structure to use, so it’s good to imagine how the current data may look if it were converted into a variety of formats, and see if that reveals any optimizations. That being said, hash tables turn out very often to be a great choice, so that’s a good place to start.

Group Sorting

Here’s another example of how changing the data structure can allow us to optimize our code. Let’s say we have an array containing several different values and we want to reorder the data so that the same values are grouped together. However, we don’t necessarily care what order the groups are in.

For example, let’s say we have the following array:

Our goal is to sort this into groups, like so:

Again, we don’t care about the order of the groups, so these results would also be acceptable:

Now, any classic sorting algorithm would accomplish our task, since we’d end up with this:

As you know, the fastest sorting algorithms clock in at O(N log N). But can we do better?

Let’s begin by coming up with the best-imaginable Big O. Since we know that there generally aren’t sorting algorithms faster than O(N log N), it may be difficult to imagine how we can sort something in a faster time.

But since we’re not doing a precise sort, if someone told me that our task can be done in O(N) time, I suppose I’d believe them. We certainly can’t beat O(N), since we need to visit each value at least once. So let’s aim for O(N).

Let’s employ the technique we’ve been discussing and imagine our data in the form of another data structure.

We may as well start with a hash table. What would our array of strings look like if it were a hash table?

If we took a similar approach to what we did with the anagrams, we could represent our array in the following way:

As with our previous example, there’s some data loss: we couldn’t convert this hash table back into our original array, as we wouldn’t know the original order of all the strings.

However, for our purposes of grouping, this data loss doesn’t matter. In fact, the hash table contains all the data we need to create the grouped array we’re looking for.

Specifically, we can iterate over each key-value pair within the hash table and use that data to populate an array with the correct number of each string. Here’s the code for this:

Our group_array function accepts an array and then begins by creating an empty hash_table and an empty new_array.

We first collect the tallies of each string and store them in the hash table:

This creates the hash table that looks like this:

Then we proceed to iterate over each key-value pair and use this data to populate the new_array:

So when we reach the pair "a": 3, we add three "a"s to the new_array. And when we reach "c": 3, we add three "c"s to the new_array, and so on. By the time we’re done, our new_array will contain all the strings organized in groups.

This algorithm takes just O(N) time, which is a significant optimization over the O(N log N) that sorting would have taken. We do use up O(N) space with the extra hash table and new_array, although we could choose to overwrite the original array to save additional memory. That being said, the space taken up by the hash table would still be O(N) in the worst case, where each string in the array is different.

But again, if speed is our goal, we achieved our best-imaginable Big O, which is a fantastic win.