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.

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:

  1. Initialization: The variable n is set to the length of nums. Then, f is initialized as a 2-dimensional list with n lists each containing n zeros.

  2. 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:

    1for i, x in enumerate(nums):
    2    f[i][i] = x
  3. 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 (from n-2 down to 0) and for each i, we iterate over the ending index j (from i+1 up to n-1).

    Within the nested loops, we calculate f[i][j], which is the best score player 1 can achieve from the current sub-array nums[i] to nums[j]. This is where player 1 may decide to pick the i-th element or the j-th element. The choice is modeled using:

    1f[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 the i-th element and thus the score is nums[i] minus the score that player 2 can subsequently achieve from the remaining sub-array (from i+1 to j).

    The second part, nums[j] - f[i][j - 1], handles the case where player 1 picks the j-th element and the score is nums[j] minus the score that player 2 can achieve from the sub-array (from i to j-1).

  4. 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 returns True.

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.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Assume our nums array is [1, 5, 2].

  1. Initialization: We set n to be 3 because there are three elements in nums. Then, we initialize our table f with zeros. It will look like this:

    1f = [
    2    [0, 0, 0],
    3    [0, 0, 0],
    4    [0, 0, 0]
    5]
  2. Base Case: If there's only one element, player 1 will pick that element. So f[0][0], f[1][1], and f[2][2] will simply be 1, 5, and 2 respectively. The updated table f is:

    1f = [
    2    [1, 0, 0],
    3    [0, 5, 0],
    4    [0, 0, 2]
    5]
  3. 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 at j = 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.
    • Now for the sub-array starting at i = 0 and ending at j = 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.

    Our f table now looks like this:

    1f = [
    2    [1, 4, 0],
    3    [0, 5, 3],
    4    [0, 0, 2]
    5]
    • Lastly, for the entire array (i = 0 to j = 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, so f[0][2] = max(-2, -2) = -2.

    The final f table is:

    1f = [
    2    [1, 4, -2],
    3    [0, 5, 3],
    4    [0, 0, 2]
    5]
  4. Evaluation: We examine f[0][2], which is the score of player 1 after considering the entire array. Since f[0][2] = -2, player 1 is not guaranteed to win; player 2 has an advantage. Therefore, the answer is False.

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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, where n is the length of the nums 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).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫