Algorithm
Problem Name: 486. Predict the Winner
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.
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.
Constraints:
1 <= nums.length <= 20
0 <= nums[i] <= 107
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define MAX_LEN 20
#define IDX(S, E) ((S) * (MAX_LEN) + (E))
typedef struct {
bool flag;
int val;
} m_t;
int _max(int a, int b) {
if (a > b) return a;
return b;
}
int helper(int *nums, int s, int e, m_t *mem) {
int a, b, c;
m_t *m;
if (s == e) {
c = nums[s];
} else {
a = nums[s]; // pick the first one
m = &mem[IDX(s + 1, e)]; // the rest
if (m->flag) {
a -= m->val;
} else {
a -= helper(nums, s + 1, e, mem);
}
b = nums[e]; // pick the last one
m = &mem[IDX(s, e - 1)]; // the rest
if (m->flag) {
b -= m->val;
} else {
b -= helper(nums, s, e - 1, mem);
}
c = _max(a, b);
}
// save it
m = &mem[IDX(s, e)];
m->flag = 1;
m->val = c;
return c;
}
bool PredictTheWinner(int* nums, int numsSize){
m_t mem[MAX_LEN * MAX_LEN] = { 0 };
if (helper(nums, 0, numsSize - 1, mem) >= 0) return true;
return false;
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
vector<int>score(2);
return solve(nums, score, 0, 0, nums.size() - 1);
}
bool solve(vector<int>& nums, vector<int>& score, int player, int l, int r) {
if (l >= r) {
return score[0] >= score[1];
}
if (player == 0) {
// Pick left
score[0] += nums[l];
if (solve(nums, score, player ^ 1, l + 1, r)) {
score[0] -= nums[l];
return true;
}
score[0] -= nums[l];
// Pick right
score[0] += nums[r];
if (solve(nums, score, player ^ 1, l, r - 1)) {
score[0] -= nums[r];
return true;
}
score[0] -= nums[r];
} else {
// Pick left
score[1] += nums[l];
if (!solve(nums, score, player ^ 1, l + 1, r)) {
score[1] -= nums[l];
return false;
}
score[1] -= nums[l];
// Pick right
score[1] += nums[r];
if (!solve(nums, score, player ^ 1, l, r - 1)) {
score[1] -= nums[r];
return false;
}
score[1] -= nums[r];
}
return player;
}
};
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const PredictTheWinner = function(nums) {
// The dp[i][j] saves how much more scores that the first-in-action player will get from i to j than the second player.
const dp = [];
for (let i = 0; i < = nums.length; i++) {
dp.push(Array(nums.length).fill(0));
}
for (let s = nums.length - 1; s >= 0; s--) {
dp[s][s] = nums[s];
for (let e = s + 1; e < nums.length; e++) {
let a = nums[s] - dp[s + 1][e];
let b = nums[e] - dp[s][e - 1];
dp[s][e] = Math.max(a, b);
}
}
return dp[0][nums.length - 1] >= 0;
};
console.log(PredictTheWinner([1, 5, 233, 7]));
console.log(PredictTheWinner([3, 5, 3]));
Copy The Code &
Try With Live Editor
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def PredictTheWinner(self, nums):
def dfs(l, r, p1, p2, turn):
if l > r:
return p1 >= p2
elif turn:
return dfs(l + 1, r, p1 + nums[l], p2, 0) or dfs(l, r - 1, p1 + nums[r], p2, 0)
else:
return dfs(l + 1, r, p1, p2 + nums[l], 1) and dfs(l, r - 1, p1, p2 + nums[r], 1)
return dfs(0, len(nums) - 1, 0, 0, 1)
Copy The Code &
Try With Live Editor
Input
Output