Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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.

Similar Problem

Maximum gain in a two-player game with picking elements from array ends

Solution

Method 1 - Recursion

Here is the approach:

  1. Base Condition: If there is only one element left in the array, Player 1 picks it, so we return that value.
  2. Recurrence Relation: For each subarray nums[i...j], Player 1 can choose either nums[i] or nums[j]. Player 1 then aims to maximize their net score (their score minus Player 2’s score) after Player 2’s optimal play on the remaining subarray.
    • If Player 1 picks nums[i], Player 2 will play optimally on nums[i+1...j].
    • If Player 1 picks nums[j], Player 2 will play optimally on nums[i...j-1].
    • Thus, the recursive formula is max(nums[i] - helper(i+1, j), nums[j] - helper(i, j-1)).

Code

1
2
3
4
5
6

public boolean predictTheWinner(int[] nums) {
	return helper(nums, 0, nums.length-1)>=0;
}
private int helper(int[] nums, int s, int e){        
	return s==e ? nums[e] : Math.max(nums[e] - helper(nums, s, e-1), nums[s] - helper(nums, s+1, e));
}
1
2
3
4
5
6
7

def predictTheWinner(nums):
    def helper(i, j):
        if i == j:
            return nums[i]
        return max(nums[i] - helper(i + 1, j), nums[j] - helper(i, j - 1))

    return helper(0, len(nums) - 1) >= 0

Complexity

  • Time: O(2^n)
  • Space: O(n)

Method 2 - Top Down DP

Here is the memoized solution:

  1. Array Initialization: Create a memoization table memo to store intermediate results.
  2. Base Condition: If there is only one element left in the array, Player 1 picks it, so we return that value.
  3. Recurrence Relation: For each subarray nums[i...j], Player 1 can choose either nums[i] or nums[j]. Player 1 then aims to maximize their net score (their score minus Player 2’s score) after Player 2’s optimal play on the remaining subarray.
    • If Player 1 picks nums[i], Player 2 will play optimally on nums[i+1...j].
    • If Player 1 picks nums[j], Player 2 will play optimally on nums[i...j-1].
    • Use the memoization table memo to store and retrieve previously computed results.
    • Thus, the recursive formula is max(nums[i] - helper(i+1, j), nums[j] - helper(i, j-1)).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        Integer[][] memo = new Integer[n][n];
        return helper(nums, 0, n - 1, memo) >= 0;
    }

    private int helper(int[] nums, int i, int j, Integer[][] memo) {
        if (i > j) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (i == j) {
            memo[i][j] = nums[i];
        } else {
            memo[i][j] = Math.max(nums[i] - helper(nums, i + 1, j, memo),
                nums[j] - helper(nums, i, j - 1, memo));
        }
        return memo[i][j];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def predictTheWinner(nums):
    n = len(nums)
    memo = [[None] * n for _ in range(n)]

    def helper(i, j):
        if i > j:
            return 0
        if memo[i][j] is not None:
            return memo[i][j]
        if i == j:
            memo[i][j] = nums[i]
        else:
            memo[i][j] = max(
                nums[i] - helper(i + 1, j), nums[j] - helper(i, j - 1)
            )
        return memo[i][j]

    return helper(0, n - 1) >= 0

Complexity

  • ⏰ Time complexity: O(n^2), because we are filling up an n x n memoization table
  • 🧺 Space complexity: O(n^2), due to the memoization table used to store intermediate results and the recursion stack, which is bound by O(n), but typically the memoization table dominates.

Method Bottom up - TD DP

Here is the approach:

  1. Array Initialization: Create a 2D array dp where dp[i][j] represents the maximum score Player 1 can achieve over Player 2 from the subarray nums[i...j].
  2. Base Condition: For subarrays of one element, dp[i][i] = nums[i], since Player 1 takes the only available number.
  3. Fill the DP Table: For each subarray nums[i...j], Player 1 can choose either nums[i] or nums[j]. Player 1 then aims to maximize their net score (their score minus Player 2’s score) after Player 2’s optimal play on the remaining subarray.
    • If Player 1 picks nums[i], Player 2 will play optimally on nums[i+1...j].
    • If Player 1 picks nums[j], Player 2 will play optimally on nums[i...j-1].
    • Thus, dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public boolean canWin(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];

        // Fill the dp array for subarrays of increasing length
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (i == j) {
                    dp[i][j] = nums[i];
                } else {
                    dp[i][j] = Math.max(
                        nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
                }
            }
        }

        // Check if Player 1 can win starting with the entire array
        return dp[0][n - 1] >= 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def canWin(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    # Fill the dp array for subarrays of increasing length
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if i == j:
                dp[i][j] = nums[i]
            else:
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])

    # Check if Player 1 can win starting with the entire array
    return dp[0][n - 1] >= 0

Complexity

  • Time: O(n^2)
  • Space: O(n^2)