Pular para o conteúdo principal

Predict the Winner

This question is asked by Amazon. Given an integer array, two players take turns picking the largest number from the ends of the array. First, player one picks a number (either the left end or right end of the array) followed by player two. Each time a player picks a particular number, it is no longer available to the other player. This picking continues until all numbers in the array have been chosen. Once all numbers have been picked, the player with the larger score wins. Return whether or not player one will win.

Note: You may assume that each player is playing to win (i.e. both players will always choose the maximum of the two numbers each turn) and that there will always be a winner.

Example(s)​

Example 1:

Input: nums = [1, 2, 3]
Output: true
Explanation:
Turn 1: Player 1 picks 3 (right end)
Turn 2: Player 2 picks 2 (left end, since 2 > 1)
Turn 3: Player 1 picks 1 (only remaining)
Scores: Player 1 = 3 + 1 = 4, Player 2 = 2
Player 1 wins (4 > 2)

Example 2:

Input: nums = [1, 5, 2]
Output: false
Explanation:
Turn 1: Player 1 picks 5 (middle, but can only pick ends: 1 or 2)
  Actually, Player 1 picks 2 (right end, since 2 > 1)
Turn 2: Player 2 picks 5 (only remaining end)
Turn 3: Player 1 picks 1 (only remaining)
Scores: Player 1 = 2 + 1 = 3, Player 2 = 5
Player 2 wins (5 > 3)

Example 3:

Input: nums = [1, 5, 233, 7]
Output: true
Explanation:
Player 1 can win with optimal play.

Example 4:

Input: nums = [1, 1]
Output: true
Explanation:
Both players get 1, so player 1 wins (ties go to player 1, or we can say >= 0 means win).

Solution​

The solution uses Dynamic Programming:

  1. DP state: dp[i][j] = maximum score difference player 1 can achieve over player 2 for subarray nums[i...j]
  2. Base case: dp[i][i] = nums[i] (single element, player 1 gets it)
  3. Recurrence: dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
  4. Result: dp[0][n-1] >= 0 means player 1 wins

JavaScript Solution - Dynamic Programming

/**
* Check if player 1 can win
* @param {number[]} nums - Array of numbers
* @return {boolean} - Whether player 1 wins
*/
function predictTheWinner(nums) {
const n = nums.length;

// dp[i][j] = maximum score difference player 1 can achieve over player 2
// for subarray nums[i...j] (player 1's score - player 2's score)
const dp = Array(n).fill().map(() => Array(n).fill(0));

// Base case: single element, player 1 gets it
for (let i = 0; i < n; i++) {
  dp[i][i] = nums[i];
}

// Fill DP table: length from 2 to n
for (let len = 2; len <= n; len++) {
  for (let i = 0; i <= n - len; i++) {
    const j = i + len - 1;
    
    // Player 1 can pick either end:
    // Option 1: Pick left (nums[i]), player 2 gets optimal for nums[i+1...j]
    // Option 2: Pick right (nums[j]), player 2 gets optimal for nums[i...j-1]
    // Score difference = chosen value - opponent's optimal difference
    dp[i][j] = Math.max(
      nums[i] - dp[i + 1][j],  // Pick left
      nums[j] - dp[i][j - 1]   // Pick right
    );
  }
}

// If dp[0][n-1] >= 0, player 1 wins (or ties)
return dp[0][n - 1] >= 0;
}

// Test cases
console.log('Example 1:', predictTheWinner([1, 2, 3])); 
// true

console.log('Example 2:', predictTheWinner([1, 5, 2])); 
// false

console.log('Example 3:', predictTheWinner([1, 5, 233, 7])); 
// true

console.log('Example 4:', predictTheWinner([1, 1])); 
// true
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Space-Optimized)​

Here's a space-optimized version using only O(n) space:

/**
 * Space-optimized: O(n) space instead of O(n²)
 */
function predictTheWinnerOptimized(nums) {
  const n = nums.length;
  
  // dp[i] = maximum score difference for subarray starting at i
  // We process by length, so we only need one row
  const dp = [...nums]; // Initialize with single elements
  
  // Fill DP table: length from 2 to n
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      // Update dp[i] for current length
      dp[i] = Math.max(
        nums[i] - dp[i + 1],  // Pick left
        nums[j] - dp[i]       // Pick right (need to save previous value)
      );
    }
  }
  
  // Actually, this optimization is tricky. Let's use the standard approach.
  // The O(n²) space is acceptable for clarity.
  return predictTheWinner(nums);
}

Complexity​

  • Time Complexity: O(n²) - Where n is the length of the array. We fill a DP table of size n × n.
  • Space Complexity: O(n²) - For the DP table. Can be optimized to O(n) but it's more complex.

Approach​

The solution uses Dynamic Programming with game theory:

  1. DP state:

    • dp[i][j] = maximum score difference player 1 can achieve over player 2 for subarray nums[i...j]
    • Positive value means player 1 wins, negative means player 2 wins

  2. Base case:

    • dp[i][i] = nums[i] - Single element, player 1 gets it (score difference = nums[i])

  3. Recurrence:

    • Player 1 can pick either end:
      • Pick left (nums[i]): Player 2 gets optimal for nums[i+1...j]
        • Score difference = nums[i] - dp[i+1][j]
      • Pick right (nums[j]): Player 2 gets optimal for nums[i...j-1]
        • Score difference = nums[j] - dp[i][j-1]
    • dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])

  4. Result:

    • If dp[0][n-1] >= 0, player 1 wins (or ties)

Key Insights​

  • Game theory: Both players play optimally
  • Score difference: Track difference, not absolute scores
  • Optimal substructure: Optimal play for subarray uses optimal play for smaller subarrays
  • O(n²) time: Must consider all subarrays
  • Minimax: Player 1 maximizes, player 2 minimizes (handled by subtracting)

Step-by-Step Example​

Let's trace through Example 1: nums = [1, 2, 3]

nums = [1, 2, 3]
n = 3

DP table (dp[i][j]):
        j:  0  1  2
  i=0:      1  ?  ?
  i=1:      -  2  ?
  i=2:      -  -  3

Base cases:
  dp[0][0] = 1
  dp[1][1] = 2
  dp[2][2] = 3

Fill by length:
  Length 2:
    dp[0][1]: max(nums[0] - dp[1][1], nums[1] - dp[0][0])
            = max(1 - 2, 2 - 1)
            = max(-1, 1)
            = 1
    
    dp[1][2]: max(nums[1] - dp[2][2], nums[2] - dp[1][1])
            = max(2 - 3, 3 - 2)
            = max(-1, 1)
            = 1
  
  Length 3:
    dp[0][2]: max(nums[0] - dp[1][2], nums[2] - dp[0][1])
            = max(1 - 1, 3 - 1)
            = max(0, 2)
            = 2

Result: dp[0][2] = 2 >= 0 → true (player 1 wins)

Game play:
  Player 1 picks 3 (right): score = 3, difference = 3
  Player 2 picks 2 (left): score = 2, difference = 3 - 2 = 1
  Player 1 picks 1: score = 3 + 1 = 4, difference = 4 - 2 = 2
  Player 1 wins!

Visual Representation​

Example 1: nums = [1, 2, 3]

DP table:
        j:  0  1  2
  i=0:      1  1  2
  i=1:      -  2  1
  i=2:      -  -  3

Game play:
  Turn 1: Player 1 picks 3 (right end)
    Remaining: [1, 2]
    Player 1 score: 3
  
  Turn 2: Player 2 picks 2 (left end, since 2 > 1)
    Remaining: [1]
    Player 2 score: 2
  
  Turn 3: Player 1 picks 1
    Remaining: []
    Player 1 score: 3 + 1 = 4
  
  Result: Player 1 wins (4 > 2)

Example 2: nums = [1, 5, 2]

DP table:
        j:  0  1  2
  i=0:      1  ?  ?
  i=1:      -  5  ?
  i=2:      -  -  2

  dp[0][1] = max(1-5, 5-1) = max(-4, 4) = 4
  dp[1][2] = max(5-2, 2-5) = max(3, -3) = 3
  dp[0][2] = max(1-3, 2-4) = max(-2, -2) = -2

Result: dp[0][2] = -2 < 0 → false (player 2 wins)

Edge Cases​

  • Single element: Player 1 wins (gets the element)
  • Two elements: Player 1 picks larger, player 2 gets smaller
  • All same: Player 1 wins (or ties, depending on interpretation)
  • Even length: Player 1 may have advantage or disadvantage
  • Odd length: Player 1 may have advantage

Important Notes​

  • Optimal play: Both players choose maximum available
  • Score difference: We track difference, not absolute scores
  • Game theory: Minimax principle (player 1 maximizes, player 2 minimizes)
  • O(n²) time: Must consider all subarrays
  • Ties: If difference is 0, player 1 wins (>= 0)

Why Dynamic Programming Works​

Optimal Substructure:

  • To find optimal play for nums[i...j], we need:
    • Optimal play for nums[i+1...j] (if pick left)
    • Optimal play for nums[i...j-1] (if pick right)
  • The optimal solution uses optimal solutions to subproblems

Overlapping Subproblems:

  • Multiple game states may share the same subarrays
  • DP stores and reuses these optimal values

Game Theory Insight​

This is a zero-sum game where:

  • Player 1 wants to maximize score difference
  • Player 2 wants to minimize score difference (maximize their own)
  • Both play optimally
  • The DP recurrence dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) captures this:
    • Player 1 picks the option that maximizes their advantage
    • The subtraction accounts for player 2's optimal response
  • Stone Game: Similar game theory problem
  • Stone Game II: Variation with different rules
  • Nim Game: Different game theory problem
  • Can I Win: Different game theory problem

Takeaways​

  • Dynamic Programming solves this efficiently
  • Game theory with optimal play from both players
  • Score difference tracking simplifies the problem
  • O(n²) time to fill DP table
  • Classic DP problem with game theory application