Recognizing Patterns

One of the most helpful strategies for both code optimization and algorithm development in general is to find patterns within the problem at hand. Often, the discovery of a pattern can help you cut through all the complexity of a problem and develop an algorithm that is simple.

The Coin Game

Here’s a great example. A game I call “the coin game” has two players who compete in the following way: they start with a pile of coins, and each player has the choice of removing either one or two coins from the pile. The player who removes the last coin loses. Fun, right?

It turns out that this isn’t a game of random chance, and with the right strategy, you can force your opponent to take the last coin and lose the game. To make this clear, let’s start with some really small coin piles and see how the game plays out.

If there’s just one coin in the pile, the player whose turn it is loses, since they have no choice but to take the last coin.

If there are two coins left, the player whose turn it is can force a win. This is because they can take just one coin and thereby force their opponent to take the final coin.

When there are three coins remaining, the player whose turn it is can also force a win, since they can remove two coins, forcing their opponent to take the final coin.

Now, when there are four coins left, the current player is in trouble. If they remove one coin, the opponent is given a pile of three coins, which we established earlier can allow that player to force a win. Similarly, if the current player removes two coins, the opponent is left with two coins, which can also allow the opponent to force a win.

If we were to write a function that calculated whether you can win the game when presented with a coin pile of a given size, what approach should we take? If we think about this carefully, we may realize we can use subproblems to help calculate an accurate result for any number of coins. This would make top-down recursion a natural fit for solving this problem.

Here’s a Python implementation of a recursive approach:

This game_winner function is given a number of coins and the player whose turn it is (either "you" or "them"). The function then returns either "you" or "them" as the winner of the game. When the function is first called, the current_player is "you".

We define our base case as when the current_player is dealt 0 or fewer coins. This means the other player took the last coin and the current player, by default, won the game.

We then define a next_player variable, which keeps track of which player will go next.

Then we do our recursion. We recursively call our game_winner function on piles of coins that are both one and two coins smaller than the current pile, and see if the next player would win or lose in those scenarios. If the next_player loses in both scenarios, that means the current_player will win.

This isn’t an easy algorithm, but we pulled it off. Now let’s see if we can optimize it.

To satisfy our prereq, we first need to figure out our algorithm’s current speed.

You may have noticed that this function makes multiple recursive calls. If alarm bells are going off in your head, that’s for good reason. The time complexity of this function is a whopping O(2^N), which can be unbearably slow.

We can improve this by using the memoization technique you learned about in Chapter 12, , which could bring the speed up to O(N), with N being the number of coins in the starting pile. That’s a huge improvement.

But let’s see if we can push our algorithm’s speed even further.

To determine whether we can optimize our algorithm further, we need to ask ourselves what we think the best-imaginable Big O is.

Because N is just a single number, I could conceive that we can make an algorithm that takes just O(1) time. Since we don’t actually have to touch N items in an array or anything like that, if someone told me they figured out an algorithm for the coin game that was just O(1), I’d believe them. So let’s strive for O(1).

But how do we get there? This is where finding a pattern can help.

Generating Examples

While each problem has a unique pattern, I found a technique for finding patterns that helps across all problems—and that is to generate numerous examples. This means we should take a bunch of example inputs, calculate their respective outputs, and see if we can detect a pattern.

Let’s apply this to our case.

If we map out who wins for coin piles of size 1 through 10, we get this table:

The pattern becomes clear when we lay it out this way. Basically, starting with 1 coin, every third number gives victory to the opponent. Otherwise, you are the winner.

So if we take the number of coins and subtract 1, each "them" ends up at a number that is divisible by 3. At this point, then, we can determine who will win based on a single division calculation:

This code is saying that if after subtracting 1, the number_of_coins is divisible by 3, the winner is "them". Otherwise, "you" are the winner.

Because this algorithm consists of a single mathematical operation, it’s O(1) in both time and space. It’s also a lot simpler! This is a real win-win-win.

By generating many examples of coin piles (as inputs) and seeing who’d win the game (as outputs), we were able to identify a pattern in how the coin game works. We were then able to use this pattern to cut to the heart of the problem and turn a slow algorithm into an instantaneous one.

The Sum Swap Problem

Here’s an example where we can use both pattern recognition and magical lookups together to optimize an algorithm.

The next problem, known as the sum swap problem, goes like this:

We want to write a function that accepts two arrays of integers. As an example, let’s say these are our arrays:

Currently, the numbers in array_1 add up to 20, while the numbers in array_2 add up to 18.

Our function needs to find one number from each array that can be swapped to cause the two array sums to be equal.

In this example, if we swapped the 2 from array_1 and the 1 from array_2, we’d get:

And both arrays would now have the same sum—namely, 19.

To keep things simple, our function won’t actually perform the swap but will return the two indexes that we’d have to swap. We can do this as an array containing the two indexes. So, in this case, we swapped index 2 of array_1 with index 0 of array_2, so we’ll return an array of [2, 0]. In a case where there’s no possible swap that makes the two arrays equal, we’ll return None.

One way we can write this algorithm is to use nested loops; that is, as our outer loop points to each number from array_1, an inner loop can iterate over each number from array_2 and test the sums of each array if we were to swap the two numbers.

To begin optimizing this, we must first satisfy our prereq of knowing the Big O of our current algorithm.

Because our nested-loops approach visits M numbers from the second array for each of the N numbers of the first array, this algorithm is O(N * M). (I’m discussing N and M because the arrays may be two different sizes.)

Can we do better? To find out, let’s determine what we think the best-imaginable Big O may be.

It would seem that we absolutely have to visit each number from the two arrays at least once, since we need to be aware of what all the numbers are. But it’s possible that this may be all we need to do. If so, this would be O(N + M). Let’s make this our best-imaginable Big O and aim for that.

Next, we need to try to dig up any patterns hidden within the problem. Again, the best technique to dig up patterns is to come up with numerous examples and look for patterns among them.

So let’s look at a number of different examples where swapping numbers will cause the two arrays to have equal sums, as shown in the .

In looking at these examples, a few patterns begin to emerge. Some of these patterns may seem obvious, but let’s look at them anyway.

One pattern is that to achieve equal sums, the larger array needs to trade a larger number with a smaller number from the smaller array.

A second pattern is that with a single swap, each array’s sum changes by the same amount. For example, when we swap a 7 with a 4, one array’s sum decreases by 3, while the other array’s sum increases by 3.

A third interesting pattern is that the swaps always cause the two array sums to fall out exactly in the middle of where the two array sums began.

In the first case, for example, array_1 was 18 and array_2 was 12. When making a correct swap, the two arrays land at 15, which is exactly in the middle between 18 and 12.

When we think about it further, this third pattern is a logical outgrowth of the other patterns. Since a swap causes the two arrays to shift their sums by the same amount, the only way to make their sums equal is to meet in the middle.

Based on this, if we know the sums of the two arrays, we should be able to look at any number in one of the arrays and calculate what number it should be swapped with.

Let’s take this example again:

We know that for a swap to work successfully, we’ll need the two arrays’ sums to land in the middle. The exact middle between 18 and 12 is 15.

Let’s look at different numbers from array_1 and figure out what number we’d want to swap it with. We can call this other number its counterpart. Let’s start with the first number from array_1, which is the number 5.

What number would we want to swap the 5 with? Well, we know that we want array_1 to decrease by 3, and array_2 to increase by 3, so we’d need to swap the 5 with a number 2. It just so happens that array_2 doesn’t contain a 2, so the 5 cannot be successfully swapped with any number from array_2.

If we look at the next number from array_1, it’s a 3. We’d have to swap this with a 0 from array_2 to get the two sums to be equal. Alas, a 0 doesn’t exist in array_2.

The last number from array_1, though, is a 7. We can calculate that we’d want to swap the 7 with a 4 to make the sums both land at 15. Luckily, array_2 does contain a 4, so we can make a successful swap.

So, how do we express this pattern in code?

Well, we can first determine how much an array sum needs to shift using this calculation:

Here, sum_1 is the sum of array_1, and sum_2 is the sum of array_2. If sum_1 is 18 and sum_2 is 12, we end up with a difference of 6. We then divide that by 2 to determine how much each array needs to shift. This is the shift_amount.

In this case, the shift_amount is 3, indicating that array_2 needs to increase by 3 to hit the target sum. (Likewise, array_1 needs to decrease by 3.)

So we can start building our algorithm by first calculating the sums of the two arrays. We can then loop through all the numbers in one of the arrays and look for the counterpart in the other.

If we were to iterate over each number in array_2, for example, we know that the current number would have to be swapped with its counterpart, which would be the current number plus the shift_amount. For example, if the current number is 4, to find its counterpart, we add the shift_amount(3) to it and get 7. This means we need to find a 7 in array_1 to swap with our current number.

So, we’ve figured out that we can look at any number in either array and know exactly what its counterpart from the other array should be. But how does this help? Don’t we still need to use nested loops and have an algorithm that is O(N * M)? That means that for each number in one array, we have to search the entire other array for the counterpart.

This is where we can invoke magical lookups and ask ourselves, “If I could magically find a desired piece of information in O(1) time, can I make my algorithm faster?”

Indeed, if we could find a number’s counterpart from the other array in just O(1) time, our algorithm would be much faster. And we can achieve those quick lookups by following the usual technique of bringing in our good ol’ hash table.

If we first store the numbers from one array in a hash table, we can then immediately find any number from it in O(1) time as we iterate through the other array.

Here’s the complete code:

This approach is much faster than our original O(N * M) one. If we consider array_1 to be N and array_2 to be M, we could say that this algorithm runs in O(N + M) time. While we do iterate over array_2 twice and it is technically 2M, it becomes M since we drop the constants.

This approach takes up an extra O(N) space since we copy all N numbers from array_1 into the hash table. Again, we’re sacrificing space to gain time, but this is a big win if speed is our primary concern.

In any case, this is another example of where discovering patterns allows us to cut to the heart of the problem and develop a simple and fast solution.