Predict The Winner - Leetcode Solution

Problem Statement:

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Solution:

The problem is asking us to determine if player 1 can win, given that both player 1 and player 2 will play optimally. We can solve this problem using recursion and memoization. The recursive function will simulate the game, and will try all the possible choices for player 1 and player 2.

For each recursive call, we will keep track of the range of the array that is currently available for picking and also, we will keep track of the scores of player 1 and player 2. Since the function will be called multiple times with the same inputs, we will use memoization to avoid recomputation.

Algorithm:

1. Define a recursive function “winner” that takes in the range of the array that is currently available for picking and the scores of player 1 and player 2. The function will return the maximum score that player 1 can get from the remaining array.

2. Base Case: If the range of the array is empty, return the difference in scores of the two players. If player 1 has more points than player 2, return a positive number, indicating that player 1 has won. If player 2 has more points than player 1, return a negative number, indicating that player 2 has won. If the scores of both players are equal, return 0, indicating a tie.

3. Check if we have computed the result of the current subproblem before. If so, return the memoized result.

4. For player 1, we can choose either the first element or the last element of the current range. If we choose the first element, the new range will be [start+1, end] and the scores of player 1 and player 2 will increase by nums[start] and 0 respectively. If we choose the last element, the new range will be [start, end-1] and the scores of player 1 and player 2 will increase by nums[end] and 0 respectively.

5. For player 2, we will choose either the first element or the last element of the remaining array. If the player chooses the first element, the new range will be [start+1, end] and the scores of player 1 and player 2 will remain the same. If the player chooses the last element, the new range will be [start, end-1] and the scores of player 1 and player 2 will remain the same.

6. For each choice that player 1 makes, we will recursively call the “winner” function, passing in the new range and the updated scores of player 1 and player 2. We will take the maximum of all the results obtained from these recursive calls. This is because player 1 will choose the move that will result in the maximum score for him.

7. Store the result obtained from the current subproblem in the memoization table.

8. Return the maximum score that player 1 can get from the remaining array.

Code:

The code for the above algorithm is given below:

class Solution:

def winner(self, nums, start, end, memo):

    # Base case: if the range of the array is empty
    if start > end:
        return 0

    # Check if we have computed the result of the current subproblem before
    if (start, end) in memo:
        return memo[(start, end)]

    # Possible moves for player 1
    pick_start = nums[start] + self.winner(nums, start+1, end, memo)
    pick_end = nums[end] + self.winner(nums, start, end-1, memo)

    # Possible moves for player 2
    next_pick_start = self.winner(nums, start+1, end, memo)
    next_pick_end = self.winner(nums, start, end-1, memo)

    # Store the result obtained from the current subproblem in the memoization table
    memo[(start, end)] = max(pick_start - next_pick_start, pick_end - next_pick_end)

    # Return the maximum score that player 1 can get from the remaining array
    return memo[(start, end)]


def PredictTheWinner(self, nums: List[int]) -> bool:
    
    n = len(nums)
    memo = {}
    
    # Determine if player 1 can win
    return self.winner(nums, 0, n-1, memo) >= 0

The time complexity of the above solution is O(n^2), where n is the length of the input array. This is because we are solving n^2 subproblems and each subproblem takes O(1) time to solve.

Conclusion:

In this article, we have discussed how to solve the “Predict the Winner” problem on LeetCode. We have used recursion and memoization to simulate the game, and we have determined whether player 1 can win or not. The solution has a time complexity of O(n^2) and avoids recomputation using memoization.

1