We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Predict the Winner

Number: 486

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Cisco, Uber, TikTok, Adobe, Flipkart, Salesforce

Problem Description

Given an array of numbers, two players take turns picking a number from either end of the array. Player 1 starts first. Each number chosen is added to the player's score. Both players play optimally. Return true if Player 1 can win (or tie, which also counts as a win for Player 1), otherwise return false.

Key Insights

  • The problem is a two-player game where both players make optimal choices.
  • We can treat the game as a zero-sum game where one player’s gain is another player’s loss.
  • A recursive approach can be used to simulate the game by considering all possible decisions.
  • Use dynamic programming (memoization) to avoid recalculating subproblems and improve efficiency.
  • Define a helper function dp(i, j) that returns the maximum score difference the current player can achieve from the subarray nums[i...j].
  • The final decision is based on whether the computed difference is non-negative, which means Player 1 can at least tie.

Space and Time Complexity

Time Complexity: O(n^2) – every subarray (i, j) is computed once. Space Complexity: O(n^2) – for the memoization table.

Solution

The solution uses recursion with memoization. We define a function dp(i, j) which computes the maximum score difference the current player can achieve over their opponent for the subarray from index i to j. On the current player's turn, they have two choices:

  1. Pick the left number nums[i] and leave the opponent with dp(i+1, j).
  2. Pick the right number nums[j] and leave the opponent with dp(i, j-1).

Since after making a move the roles are reversed, the net gain for the current player is the number picked minus the result of dp on the remaining array. The answer for the original problem is true if dp(0, n-1) >= 0.

Code Solutions

# Python solution using recursion with memoization
def predict_the_winner(nums):
    n = len(nums)
    memo = {}

    def dp(i, j):
        # Base case: only one number available to pick.
        if i == j:
            return nums[i]
        if (i, j) in memo:
            return memo[(i, j)]
        # Choice 1: pick nums[i], then the score difference is nums[i] - dp(i+1, j)
        pick_left = nums[i] - dp(i + 1, j)
        # Choice 2: pick nums[j], then the score difference is nums[j] - dp(i, j - 1)
        pick_right = nums[j] - dp(i, j - 1)
        # The current player will choose the move with the maximum difference.
        memo[(i, j)] = max(pick_left, pick_right)
        return memo[(i, j)]
    
    # Player 1 wins if the maximum difference is non-negative.
    return dp(0, n - 1) >= 0

# Example usage:
print(predict_the_winner([1,5,2]))      # Output: False
print(predict_the_winner([1,5,233,7]))  # Output: True
← Back to All Questions