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:
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:
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:
- Base Condition: If there is only one element left in the array, Player 1 picks it, so we return that value.
- Recurrence Relation: For each subarray
nums[i...j]
, Player 1 can choose eithernums[i]
ornums[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 onnums[i+1...j]
. - If Player 1 picks
nums[j]
, Player 2 will play optimally onnums[i...j-1]
. - Thus, the recursive formula is
max(nums[i] - helper(i+1, j), nums[j] - helper(i, j-1))
.
- If Player 1 picks
Code
Java
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));
}
Python
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:
- Array Initialization: Create a memoization table
memo
to store intermediate results. - Base Condition: If there is only one element left in the array, Player 1 picks it, so we return that value.
- Recurrence Relation: For each subarray
nums[i...j]
, Player 1 can choose eithernums[i]
ornums[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 onnums[i+1...j]
. - If Player 1 picks
nums[j]
, Player 2 will play optimally onnums[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))
.
- If Player 1 picks
Code
Java
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];
}
}
Python
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 ann 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 byO(n)
, but typically the memoization table dominates.
Method Bottom up - TD DP
Here is the approach:
- Array Initialization: Create a 2D array
dp
wheredp[i][j]
represents the maximum score Player 1 can achieve over Player 2 from the subarraynums[i...j]
. - Base Condition: For subarrays of one element,
dp[i][i] = nums[i]
, since Player 1 takes the only available number. - Fill the DP Table: For each subarray
nums[i...j]
, Player 1 can choose eithernums[i]
ornums[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 onnums[i+1...j]
. - If Player 1 picks
nums[j]
, Player 2 will play optimally onnums[i...j-1]
. - Thus,
dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
.
- If Player 1 picks
Code
Java
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;
}
}
Python
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)