There’s a problem on leetcode (and I imagine many other places as well) called “Predict the Winner.” If you’re unfamiliar with it, here’s the problem description:
You are given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array, followed by the player 2, followed by player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Perhaps you already know how to solve this problem. Perhaps you don’t. I found this question easy to understand on the surface, but rather difficult to think about algorithmic-ally. I grappled with it for some time before eventually having my “ah-ha” moment, which I will share with you now.
So I’m going to talk about football for a bit. Seems completely unrelated, I know, but stick with me, and see if this idea doesn’t also help you.
Imagine a football game in which the total amount of points that can be scored is fixed. You can pick any total, doesn’t matter. I’ll pick 50 for this example.
Let’s say the Dolphins are playing the Patriots and a new rule has been implemented which says that the total number of points scored between these two teams shall not exceed 50.
With this new rule in place, what does it mean whenever one team scores? In a normal football game, when one team scores, it has no major bearing on the other team’s future scoring potential. In other words, if TeamA scores 7, TeamB is free to score 7 (or more). If TeamA scores 50, nothing stops TeamB from also scoring 50 (except, you know, good defense or inept offense, but whatever). The point is, there is no limit to how high a points total each team can achieve. They are bound only by the clock.
But with our new rule in place, that is no longer the case. In my example, with 50 points as the allocated total, anytime TeamA scores, it means TeamB has lost the opportunity to ever get those points (the ones TeamA just got). Sounds obvious, but it’s an important point.
There are 50 points total. Each team aspires to get them all. So when the game starts, each team is striving for the “best they can do.” And to start with, that’s 50 points. Obviously both teams can’t get 50 points, but they both want to.
As soon as one team scores, the other must “accept” what has happened and adjust their aspirations to the new “best they can do.”
For example, if the Dolphins score 7 on their opening possession, the Patriots (who previously were hoping to get all 50 points) must now lower their expectations and accept that they best they can (now) do is 43 points. Suppose the Patriots then score 10 points. The Dolphins now, can (at best) end up with a points total of 40 (because the Patriots have taken 10 off the table). You might note that the Dolphins only need 33 more to get to 40 (and that’s true since they already have 7). But the bigger point is that when the Patriots score 10, it represents a “loss” of sorts for the Dolphins. It represents 10 points the Dolphins can never get, or, to put it another way, it represents “minus 10” for the Dolphins.
What does it mean the moment the Dolphins score their 26th point? That’s right. It means the Patriots can’t win. The new “best they can do” is 24 points, and even if they get them all, 24 is still less than 26.
What does any of this have to do with the Predict the Winner problem? Let’s suppose the game (Predict the Winner) is to be played between player 1 and player 2 using the following array of numbers:
[ 1, 5, 100, 7 ]
Each number in the array represents points that can be chosen (“scored” if you will). How many are there total? In this case, 113. When player 1 chooses first (either 1 or 7), he’s taking points “off the table” so to speak, that player 2 can never get.
If player 1 chooses 7, then of the 113 total points available, player 2’s “best he can do” has dropped to 113 – 7 = 106.
Similarly, when player 2 picks (now from either 1 or 100), he’s the one now taking points “off the table” that player 1 can never get. So if he chooses 100, player 1’s “best he can do” has dropped to 113 – 100 = 13. Once again player 1 will pick, and for this example, let’s assume he takes the 5. Player 2’s new “best he can do” has dropped to 113 – 7 – 5 = 101. And player 1 will, of course, have 12 at this point. With no more numbers left to choose, the game has ended with player 1’s total at 12 and player 2’s total at 101. What is the difference between player 1 and player 2’s scores? It’s 12 – 101 = -89.
Let’s return to football for a moment.
In football, you’ll often hear stats that refer to “differential.” Typically, you’ll hear differential used when it comes to turnovers, and usually it’s stats for the entire season. For example, if the Dolphins have a +5 differential in turnovers, it means that they recovered turnovers from their opponents 5 more times than they lost a turnover. Though you won’t hear it as often in reference to points, it still makes perfect sense. If the Dolphins beat the Patriots by a score of 14 to 7 for example, you could say the Dolphins had a point differential of +7. This idea of points differential will help us in thinking about the Predict the Winner game.
Now I should point out that knowing a differential doesn’t really tell you anything about the two actual numbers that led to that differential. If the Dolphins ended up with a points differential of +20, you’d have no way to know that they scored 35 and the Patriots scored 15, unless I had told you that there were 50 points total allocated to this game, which of course, I did (at the beginning of this article). But without that knowledge, it could have just as easily been 20 to 0, and that would have yielded the same points differential.
But, it turns out that the differential is really the only thing that matters when it comes to knowing who won (or in the case of Predict the Winner, who WILL win). Let me explain.
If player 1 chooses 7, what is the current differential at that time? It’s +7 in favor of player 1. Player 2 chooses next; let’s suppose he chooses 100. What’s the differential now (again in reference to player 1)? It’s -93. Why? Because player 1 has 7 and player 2 has 100, so player 1 is “down” by 93. Player 1 chooses again and this time chooses 5. What’s the differential now? -88 (he was down 93 and only managed to gain back 5 measly points). Finally, player 2 chooses a final time and his only option is 1. At this point, player 1’s final points differential is -89. If you think back a few paragraphs where I first described the game between player 1 and player 2, using the array [ 1, 5, 100, 7 ], player 1 ended up with 12 and player 2 ended up with 101. Who one that game? Player 2 did, obviously because 101 > 12. But something should jump out at you at this point, which is that 12 – 101 = -89 (the points differential that player 1 ended up with).
Let’s shift gears for a moment now and take a look at the recursive nature of this problem.
If we think of recursion as a tree, we can think of the left branch as the choice a player makes when he picks from the left end of the array, and the right branch as the choice the player makes when he picks from the right end of the array. Note that I didn’t say which player, and that is because they flip-flop each turn (first player 1 chooses, then player 2, then player 1, then player 2, and so on).
p1 [1, 5, 100, 7]
|
|--------------------------------|
p2 [5, 100, 7] [1, 5, 100]
|
|--------------| |-----------------|
p1 [100, 7] [5, 100] [5, 100] [1, 5]
| | | |
|-------| |--------| |------| |------|
p2 [7] [100] [100] [5] [100] [5] [5] [1]
Each level in the tree represents the options that a player has at any point in the game (I put p1 and p2 next to each level to indicate which player is picking). Player 1 goes first, and if he chooses 1, we take the first left branch of the tree, giving player 2 [5,100,7] to choose from (which is effectively just 5 and 7, since he can only choose from the ends). If player 2 chooses 7, we’ll take the right branch of the first left sub-tree, and see that player 1 will be left with [5, 100] to choose from. And then depending on whether he chooses 5 or 100, we’ll take either the left or right branch respectively, giving player 2 either 100 or 5.
How does differential come into play? At each level of recursion, a player’s differential is equal to the number he picked plus negative the number his opponent picked. Of, if you prefer, the number he picked minus the number his opponent picked.
Let’s work through an example where each player makes the best choice possible.
To start, player 1 picks first and he picks 1 (this is the best choice because picking 7 would expose the 100 to player 2, something player 1 would never be silly enough to allow). So right now:
p1_differential = player1firstPick - player2firstPick
Which works out to:
p1_differential = 1 - player2firstPick
Player 2 goes next; both of his options are equally crappy because both expose the 100 to player 1, and what’s more, whichever one he picks now, he’s stuck with the other on his next turn. Which means it doesn’t matter which he chooses right now. Let’s suppose he picks 7. In that case:
p1_differential = 1 - 7 = -6
Player 1 goes again; he picks the 100 (obviously), so his differential is now:
p1_differential = player1firstPick - player2firstPick + player1secondPick = 1 -7 + 100 = 94
Hopefully this is making sense? player 1 (if you take into account all of his choices so far and all of player 2’s) is leading by 94.
Player 2 goes again (this is his last chance to cut into player 1’s lead), and all he’s got left to choose from is the 5, so he’ll take it (even though it is of little use) and the effect on player 1’s differential is:
p1_differential = player1firstPick - player2firstPick + player1secondPick - player2SecondPick = 1 - 7 + 100 - 5 = 89
Another way to think of this is:
p1_differential = player1_pick1 - player2_pick1 + player1_pick2 -player2_pick2 + ... + player1_pickN - player2_pickN
It’s a lot like a football game isn’t it? TeamA scores, then TeamB, then TeamA, then TeamB, etc, and all along the way, you could be calculating the differential between the two Teams’ scores. Of course, each team doesn’t have to score right after the other in a real football game. TeamA might score several times before TeamB scores, but that’s ok. The basic idea still holds. At the end of it all, when you take the difference of TeamA’s score minus TeamB’s score, you get TeamA’s differential. And if TeamA’s differential is positive, TeamA won!
Ok, this is a long post I know. Let’s get to the meat and potatoes of it all. How do we translate these ideas into code? If it weren’t already obvious, recursion is definitely a viable option.
Let’s start easy. The problem statement says to determine whether player 1 will win, assuming both players play to maximize their score. So all we need to return is a true or a false.
Ok, so if there is only one number to pick from, then regardless of who is picking, that one number is the one that will be picked (obviously). If we were actually modifying the array of numbers with each recursive call, so that the length of the array we’re testing is reduced each time, then the test for a single number would be really obvious:
if (nums.length === 1) return nums[0];
Except that’s not what we’re going to do, b/c creating new arrays sucks.
Instead we’ll just use pointers to refer to the portion of the array that we want considered during each call. I’ll call those pointers i and j, and the test for a single number to pick from will look like this:
if (i === j) return nums[i];
Now if we have two or more numbers to pick from, then the picking player has two numbers to choose from: the left-most number or the right-most number. And, whichever he chooses is off-limits for the player picking next. We need name for our function, so let’s call it pick, and here’s a snippet for picking the left and picking the right.
let left = nums[i] + -pick(nums, i+1, j); let right = nums[j] + -pick(nums, i, j-1);
If at this point, you’re wondering why it’s -pick(...), remember the discussion above. A player’s differential is equal to the number he picks plus negative the next player’s pick.
Of course, all we’ve done is retrieved the differential for the left path and the right path, but we still need to determine which is the better path to take. But that’s pretty easy. Here’s the whole function:
function pick(nums, i, j) { // if one number to pick from, that's it if (i === j) return nums[i]; // see if left score is better let left = nums[i] - pick(nums, i+1, j); let right = nums[j] - pick(nums, i, j-1); return Math.max(left, right); }
Now, we’re still not quite done. We’re returning a differential with this function, but we need to return true or false. So let’s write a predictTheWinner function that kicks things off by calling our pick function and which also returns true or false as appropriate.
function PredictTheWinner(nums) { let differential = pick(nums, 0, nums.length-1); return differential >= 0; }
One quick note: the problem statement (on leetcode anyway) mentions that “if the scores of both players are equal, then player 1 is still the winner.” This why why we return differential >= 0;.
Finally, we can make our solution a bit faster with some memoization. Essentially this means remembering calculations we’ve already done and simply returning them rather than re-calculating them any time we encounter a situation where they’re needed again. Here’s what it looks like:
function PredictTheWinner(nums) { if (nums.length === 1) return true; let differential = pick(nums, 0, nums.length-1, {}); return differential >= 0; } function pick(nums, i, j, memo) { let key = i + ':' + j; if (memo[key] !== undefined) return memo[key]; // if one number to pick from, that's it if (i === j) return nums[i]; // see if left or right score is better let left = nums[i] - pick(nums, i+1, j, memo); let right = nums[j] - pick(nums, i, j-1, memo); // pick the better answer let answer = Math.max(left, right); // make a note of the answer for this point (key) memo[key] = answer; return answer; }
Hopefully this all makes sense. If you read this entire thing, i’m impressed. I almost didn’t finish writing it because its rather long. Also, my thought process is slow and sometimes convoluted. I write stuff like this primarily for my own benefit, but hopefully someone out there will benefit from it too!