algoadvance

Leetcode 486. Predict the Winner

Problem Statement

Given an array of scores that are non-negative integers. Players take turns, picking either the start or the end number from the array. The player who has the maximum score at the end wins. Determine if the player who starts can win the game, provided both players play optimally.

Return true if the first player to move can win, else return false.

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 will choose 5. 
In this scenario, player 1 will lose because his score (2 or 1) is less than player 2's score (5).

Example 2:

Input: nums = [1, 5, 233, 7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 cannot choose 233 because he has to choose between 5 and 7. 
In the next turn, player 1 chooses 233. 
Finally, player 1 has 1 + 233 = 234 points, and player 2 has 5 + 7 = 12 points.

Clarifying Questions

  1. What constraints are on the input sizes?
    • You may assume that the length of the array will not exceed 20.
  2. Can the elements within the array be 0?
    • Yes, elements can be zero as they are non-negative integers.
  3. Should the function always consider both players play optimally?
    • Yes, it should always assume optimal play for both players.

Strategy

We need to determine if the first player can guarantee a win if both players play optimally. This can be done using dynamic programming by considering the array and calculating the possible score for each player at each state.

  1. Define a DP table dp.
    • dp[i][j] will store the maximum score the current player can achieve from the subarray nums[i] to nums[j].
  2. Boundary conditions:
    • If there’s only one element (i.e., when i == j), the score for the current player is simply nums[i].
  3. Recurrence relation:
    • For more than one element, we consider two choices:
      1. Choosing the start element: nums[i] + min(dp[i+2][j], dp[i+1][j-1])
      2. Choosing the end element: nums[j] + min(dp[i+1][j-1], dp[i][j-2])
    • Both choices ensure the opponent is also making optimal choices.
  4. Final decision:
    • The result will be dp[0][n-1] compared to the sum of all elements divided by 2.
    • If dp[0][n-1] is greater than or equal to the sum of all elements divided by 2, then the first player wins.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return true;
        
        // dp array
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // Fill dp for intervals of length 1 (i == j)
        for (int i = 0; i < n; ++i) {
            dp[i][i] = nums[i];
        }
        
        // Fill dp for intervals of length > 1
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                int pickLeft = nums[i] + (i+1 <= j-1 ? min(dp[i+2][j], dp[i+1][j-1]) : 0);
                int pickRight = nums[j] + (i <= j-2 ? min(dp[i+1][j-1], dp[i][j-2]) : 0);
                dp[i][j] = max(pickLeft, pickRight);
            }
        }

        // Total sum of nums
        int total = accumulate(nums.begin(), nums.end(), 0);
        // First player win condition
        return dp[0][n-1] >= (total + 1) / 2;
    }
};

Time Complexity

This solution efficiently calculates the optimal strategy for the first player given optimal play from both players.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI