Table of Contents

# Predict the Winner – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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:falseExplanation: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:trueExplanation: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] <= 10`

^{7}

# C++ Predict the Winner LeetCode Solution

```
``````
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n)); // use to keep the score gap between player1 and player2
for (int i = 0; i < n; i++) dp[i][i] = nums[i];
for (int i = 1; i < n; i++) {
for (int j = 0; j+i < n; j++) {
dp[j][j+i] = max(nums[j+i]-dp[j][j+i-1], nums[j]-dp[j+1][j+i]);
}
}
return dp[0][n-1] >= 0; // player1 get more score points than player2
}
};
```

# Java Predict the Winner LeetCode Solution

```
``````
public class Solution {
public boolean PredictTheWinner(int[] nums) {
return helper(nums, 0, nums.length-1, new Integer[nums.length][nums.length])>=0;
}
private int helper(int[] nums, int s, int e, Integer[][] mem){
if(mem[s][e]==null)
mem[s][e] = s==e ? nums[e] : Math.max(nums[e]-helper(nums,s,e-1,mem),nums[s]-helper(nums,s+1,e,mem));
return mem[s][e];
}
}
```

# Python 3 Predict the Winner LeetCode Solution

```
``````
class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
dp = {}
def find(i, j):
if (i, j) not in dp:
if i == j:
return nums[i]
dp[i,j] = max(nums[i]-find(i+1, j), nums[j]-find(i, j-1))
return dp[i,j]
return find(0, len(nums)-1) >= 0
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1