486. Predict the Winner
Problem Description
In this problem, we are given an integer array called nums
. The game involves two players, player 1 and player 2, who take turns to pick numbers from either end of the array. Each player accumulates points based on the value of the number they pick, and the size of the array decreases by one. Player 1 starts the game. The game is over when there are no more elements left in the array to pick from.
Our task is to determine if Player 1 can win the game under the condition that both players are playing optimally. This means that each player will choose their numbers in a way that maximizes their own score. If at the end of the game, the scores are tied, Player 1 is considered the winner.
Intuition
The solution revolves around the concept of dynamic programming, where we break down this problem into smaller subproblems and solve it for each sub-array of nums
. The idea is to create a table f
where f[i][j]
represents the best score player 1 can achieve over player 2 (which might be a negative value if player 2 is leading) when considering a sub-array from index i
to index j
.
The intuition behind the dynamic programming approach is to consider each possible move for player 1 and predict the opponent's best response, which will be to minimize player 1's score. We proceed backwards, starting from the end of the array and move toward the front.
At each step, player 1 has two choices: to pick the number at the beginning or at the end of the sub-array. We simulate both choices. If player 1 picks the beginning number, the score will be nums[i] - f[i + 1][j]
. If player 1 picks the end number, the score will be nums[j] - f[i][j - 1]
. The -
sign is because player 1's choice leaves the remainder of the array to player 2, who will then be the one trying to maximize the score difference.
We then take the maximum of these two options as player 1's best strategy at this point, gradually filling up the dynamic programming table.
Finally, if f[0][n - 1]
(the best outcome starting from the entire array) is greater or equal to 0, player 1 can win the game, and we return true
.
Learn more about Recursion, Math and Dynamic Programming patterns.
Solution Approach
The provided code uses a 2-dimensional list (a matrix) f
where f[i][j]
will represent the best score player 1 can achieve more than player 2, from the sub-array of nums
starting at index i
and ending at index j
.
Here's the step-by-step implementation of the solution:
-
Initialization: The variable
n
is set to the length ofnums
. Then,f
is initialized as a 2-dimensional list withn
lists each containingn
zeros. -
Base Case: The base case is filled out where there's only one element in the sub-array (i.e.,
i == j
). In this case, the entire score is just the number itself. This is done using the loop:for i, x in enumerate(nums): f[i][i] = x
-
Dynamic Programming Table Filling: The dynamic programming table is filled in a bottom-up manner. We iterate over the starting index of the sub-array
i
in reverse (fromn-2
down to0
) and for eachi
, we iterate over the ending indexj
(fromi+1
up ton-1
).Within the nested loops, we calculate
f[i][j]
, which is the best score player 1 can achieve from the current sub-arraynums[i]
tonums[j]
. This is where player 1 may decide to pick thei-th
element or thej-th
element. The choice is modeled using:f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1])
The first part of the
max
function,nums[i] - f[i + 1][j]
, represents the scenario where player 1 picks thei-th
element and thus the score isnums[i]
minus the score that player 2 can subsequently achieve from the remaining sub-array (fromi+1
toj
).The second part,
nums[j] - f[i][j - 1]
, handles the case where player 1 picks thej-th
element and the score isnums[j]
minus the score that player 2 can achieve from the sub-array (fromi
toj-1
). -
Evaluation: In the end,
f[0][n-1]
holds player 1's best score over player 2 for the entire array. If this score is non-negative, it means that player 1 can either win or tie the game, so the method returnsTrue
.
The key algorithmic patterns used in this approach are dynamic programming and minimax. Minimax is a recursive algorithm often used in decision-making and game theory, where players minimize the possible loss for a worst-case scenario. In conjunction to dynamic programming, it helps optimize the decisions by solving subproblems once and storing their solutionsāproviding an efficient way to tackle this kind of competitive game scenario.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Assume our nums
array is [1, 5, 2]
.
-
Initialization: We set
n
to be3
because there are three elements innums
. Then, we initialize our tablef
with zeros. It will look like this:f = [ [0, 0, 0], [0, 0, 0], [0, 0, 0] ]
-
Base Case: If there's only one element, player 1 will pick that element. So
f[0][0]
,f[1][1]
, andf[2][2]
will simply be1
,5
, and2
respectively. The updated tablef
is:f = [ [1, 0, 0], [0, 5, 0], [0, 0, 2] ]
-
Dynamic Programming Table Filling: We fill the table
f
in a bottom-up manner.-
For the sub-array starting at
i = 1
(the second element) and ending atj = 2
(the last element):- The score if player 1 picks element at
i (5)
:5 - f[2][2]
(5 - 2 = 3). - The score if player 1 picks element at
j (2)
:2 - f[1][1]
(2 - 5 = -3). - Player 1 will pick the larger score, so
f[1][2] = max(3, -3) = 3
.
- The score if player 1 picks element at
-
Now for the sub-array starting at
i = 0
and ending atj = 1
:- Score if player 1 picks element at
i (1)
:1 - f[1][1]
(1 - 5 = -4). - Score if player 1 picks element at
j (5)
:5 - f[0][0]
(5 - 1 = 4). - Player 1 will choose the larger score, so
f[0][1] = max(-4, 4) = 4
.
- Score if player 1 picks element at
Our
f
table now looks like this:f = [ [1, 4, 0], [0, 5, 3], [0, 0, 2] ]
- Lastly, for the entire array (
i = 0
toj = 2
):- Score if player 1 picks first element (1):
1 - f[1][2]
(1 - 3 = -2). - Score if player 1 picks last element (2):
2 - f[0][1]
(2 - 4 = -2). - Both options result in
-2
, sof[0][2] = max(-2, -2) = -2
.
- Score if player 1 picks first element (1):
The final
f
table is:f = [ [1, 4, -2], [0, 5, 3], [0, 0, 2] ]
-
-
Evaluation: We examine
f[0][2]
, which is the score of player 1 after considering the entire array. Sincef[0][2] = -2
, player 1 is not guaranteed to win; player 2 has an advantage. Therefore, the answer isFalse
.
In this specific example, no matter how optimally player 1 plays, player 2 will always have a strategy to ensure a higher score. Thus, player 1 cannot win in this scenario.
Solution Implementation
1class Solution:
2 def PredictTheWinner(self, nums: List[int]) -> bool:
3 # Determine the total number of elements in the nums list
4 num_elements = len(nums)
5
6 # Create a 2D list (dynamic programming table) with size num_elements x num_elements
7 # where dp_table[i][j] will represent the maximum score the current player can achieve
8 # from the subarray nums[i] to nums[j]
9 dp_table = [[0] * num_elements for _ in range(num_elements)]
10
11 # Base case: When i == j, the current player can only choose nums[i]
12 for i in range(num_elements):
13 dp_table[i][i] = nums[i]
14
15 # Fill in the dp_table, starting from the end of the list and moving backwards
16 for i in range(num_elements - 2, -1, -1): # Start from second to last and go to start of the list
17 for j in range(i + 1, num_elements): # Start from just after i and move to the end of the list
18 # The current player can choose either the start or end of the remaining nums list.
19 # The score is the value chosen minus the result of the next turn (since the next turn, the opponent plays)
20 dp_table[i][j] = max(nums[i] - dp_table[i + 1][j], # If choosing the start
21 nums[j] - dp_table[i][j - 1]) # If choosing the end
22
23 # The player who starts (the one we are evaluating for winning condition) has the score
24 # at dp_table[0][num_elements - 1]. This score needs to be non-negative for the player to win.
25 return dp_table[0][num_elements - 1] >= 0
26
1class Solution {
2
3 // Function to predict the winner of the game
4 public boolean PredictTheWinner(int[] nums) {
5 int length = nums.length; // The length of the input array
6 int[][] dp = new int[length][length]; // Create a DP table to store the scores
7
8 // Initialize the diagonal of the DP table where only one element is chosen
9 for (int i = 0; i < length; ++i) {
10 dp[i][i] = nums[i];
11 }
12
13 // Fill the DP table in a bottom-up manner
14 for (int start = length - 2; start >= 0; --start) {
15 for (int end = start + 1; end < length; ++end) {
16 // For each interval [start, end], calculate the maximum score the player can achieve
17 // by choosing either the start or the end element and subtract the opponent's optimal score
18 dp[start][end] = Math.max(nums[start] - dp[start + 1][end], nums[end] - dp[start][end - 1]);
19 }
20 }
21
22 // The game is winnable if the score at the full interval [0, length - 1] is non-negative
23 return dp[0][length - 1] >= 0;
24 }
25}
26
1#include <vector>
2#include <cstring>
3#include <algorithm>
4
5class Solution {
6public:
7 // Determine if the first player to move in the game can win when both players play optimally
8 bool PredictTheWinner(vector<int>& nums) {
9 int n = nums.size(); // The number of elements in the input array 'nums'
10 vector<vector<int>> dp(n, vector<int>(n, 0)); // Initialize a 2D vector for dynamic programming
11
12 // Base cases: when only one element is considered, the player who picks it wins with that value
13 for (int i = 0; i < n; ++i) {
14 dp[i][i] = nums[i];
15 }
16
17 // Fill the DP table in a bottom-up manner
18 for (int start = n - 2; start >= 0; --start) {
19 for (int end = start + 1; end < n; ++end) {
20 // dp[start][end] represents the maximum score the player can achieve over the opponent,
21 // starting from index 'start' to index 'end' inclusive
22 dp[start][end] = std::max(nums[start] - dp[start + 1][end], nums[end] - dp[start][end - 1]);
23 }
24 }
25
26 // The winning condition: the score is non-negative
27 return dp[0][n - 1] >= 0;
28 }
29};
30
1function predictTheWinner(nums: number[]): boolean {
2 // Get the length of the nums array.
3 const numLength = nums.length;
4
5 // Create a 2D array 'dp' (short for dynamic programming)
6 // to store the maximum score difference between the two players.
7 const dp: number[][] = new Array(numLength).fill(0).map(() => new Array(numLength).fill(0));
8
9 // Initialize the diagonal of the matrix where only one number is available to pick.
10 for (let i = 0; i < numLength; ++i) {
11 dp[i][i] = nums[i];
12 }
13
14 // Build the dp matrix from the bottom up, where 'i' represents the starting index
15 // and 'j' represents the ending index of the subarray for the current game state.
16 for (let i = numLength - 2; i >= 0; --i) {
17 for (let j = i + 1; j < numLength; ++j) {
18 // Determine the best score player 1 can achieve from the current game state.
19 // It's the maximum of choosing the 'i-th' or 'j-th' number,
20 // and then subtracting the value of the dp state if the opponent picked next.
21 dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
22 }
23 }
24
25 // If the value of the dp table in the top right corner is non-negative,
26 // player 1 can win or at least tie, so return true.
27 // That value represents the score difference at the end if both play optimally.
28 return dp[0][numLength - 1] >= 0;
29}
30
Time and Space Complexity
The given code implements a dynamic programming approach to solve the game prediction problem, where two players take turns to pick from a list of numbers from either end, and the goal is to predict whether the first player can win given the player can always pick optimally.
The time complexity of this approach comes from two nested loops that iterate over the elements of the array to fill in the dynamic programming table f
:
- The outer loop runs
(n - 1)
times, wheren
is the length of thenums
list (for i in range(n - 2, -1, -1)
). - The inner loop for each
i
runs(n - i)
times (for j in range(i + 1, n)
).
We can express the total number of iterations as the sum of an arithmetic series from 1
to (n - 1)
, which gives us (n(n - 1)) / 2
. Therefore, the time complexity is O(n^2)
.
The space complexity is determined by the size of the dynamic programming table f
, which is a 2D list of size n * n
. Hence, the space complexity is also O(n^2)
.
In conclusion, the time complexity is O(n^2)
and the space complexity is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!