{x}
blog image

Predict the Winner

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

 

Example 1:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.

Example 2:

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

 

Constraints:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 107

Solution Explanation:

This problem is a classic game theory problem that can be solved efficiently using dynamic programming. The core idea is to determine whether Player 1 can guarantee a winning strategy. We can model this using recursion with memoization (or iteratively using dynamic programming).

Understanding the Game:

Two players take turns picking a number from either end of an array. The player who picks the number adds it to their score. The game continues until the array is empty. Player 1 wins if their score is greater than or equal to Player 2's score.

Recursive Approach with Memoization (Top-Down DP):

The recursive approach considers all possible choices at each step. For a subarray nums[i...j], the current player can choose either nums[i] or nums[j]. The optimal strategy for the current player is to choose the number that maximizes their advantage (their score minus the opponent's score).

The dfs function recursively calculates the maximum advantage the current player can achieve from the subarray nums[i...j].

  • Base Case: If i > j (empty subarray), the advantage is 0.
  • Recursive Step: The current player chooses either nums[i] or nums[j]. The opponent then plays optimally from the remaining subarray. The current player chooses the option that maximizes their advantage (their choice - the opponent's maximum advantage).

Memoization (using @cache in Python or a 2D array f in other languages) avoids redundant calculations, making the solution efficient.

Iterative Approach (Bottom-Up DP):

The iterative dynamic programming approach builds a solution from smaller subproblems to larger ones. It uses a 2D array f[i][j] to store the maximum advantage a player can achieve from the subarray nums[i...j].

  • Initialization: f[i][i] = nums[i] for all i (base case: single-element subarrays).
  • Iteration: The outer loop iterates through subarray sizes (from 1 to n), and the inner loops iterate through all subarrays of that size. For each subarray nums[i...j], f[i][j] is calculated as max(nums[i] - f[i+1][j], nums[j] - f[i][j-1]).

Time and Space Complexity:

  • Recursive (with memoization):

    • Time Complexity: O(n^2) due to the overlapping subproblems that memoization avoids recomputing.
    • Space Complexity: O(n^2) for the memoization table (or recursion stack without optimization).

  • Iterative (dynamic programming):

    • Time Complexity: O(n^2) due to the nested loops.
    • Space Complexity: O(n^2) for the DP table.

Example (Iterative Approach):

Let's consider nums = [1, 5, 2].

  1. Initialization: f[0][0] = 1, f[1][1] = 5, f[2][2] = 2.
  2. Iteration:
    • For subarrays of size 2:
      • f[0][1] = max(1 - 5, 5 - 1) = 4
      • f[1][2] = max(5 - 2, 2 - 5) = 3
    • For subarrays of size 3:
      • f[0][2] = max(1 - 3, 2 - 4) = -2

Since f[0][2] = -2 < 0, Player 1 cannot win.

The code provided in different languages implements either the recursive approach with memoization or the iterative approach, both achieving the same time and space complexity. The iterative approach might be slightly faster in practice due to the overhead of recursive function calls.