486. Predict the Winner - Detailed Explanation

Problem Statement

You’re given an integer array nums of length n. Two players, Player 1 and Player 2, take turns picking a number from either end of the array. Each picked number is added to that player’s score, and the number is removed from the array. Player 1 goes first. Both players play optimally to maximize their own score. Return true if Player 1 can guarantee a score ≥ Player 2’s score by the end, otherwise return false.

Examples

Example 1

Input: nums = [1,5,2]
Output: false
Explanation: Player 1 chooses 1 or 2.
If Player 1 picks 1, nums→[5,2], Player 2 picks 5, Player 1 picks 2 → scores (1+2)=3 vs 5.
If Player 1 picks 2, nums→[1,5], Player 2 picks 5 → scores 2 vs (1+5)=6.
Player 1 cannot win.

Example 2

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 picks 1 → [5,233,7], Player 2 best picks 7 → [5,233], Player 1 picks 233 → [5], Player 2 picks 5.
Scores: Player 1 = 1+233 = 234, Player 2 = 7+5 = 12.

Constraints

• 1 ≤ n = nums.length ≤ 20
• 0 ≤ nums[i] ≤ 10⁷

Hints

1. Define a helper that returns the score difference (current player score − opponent score) achievable on subarray [i…j].
2. If you pick left, your net gain is nums[i] − dfs(i+1,j). Picking right yields nums[j] − dfs(i,j-1). Choose the max.
3. You can memoize the recursion to avoid exponential blowup.
4. Alternatively, set up a bottom‑up DP over all subarray lengths.

Approach 1 – Recursive Minimax with Memoization

Idea

Let dfs(i, j) = maximum net score difference the current player can achieve over the opponent on nums[i…j].

• Base: if i == j, you pick that only element → return nums[i].
• Recurrence: you choose left or right to maximize your net gain:

  pickLeft  = nums[i]   − dfs(i+1, j)  
  pickRight = nums[j]   − dfs(i, j-1)  
  dfs(i,j) = max(pickLeft, pickRight)  
  

Player 1 wins if dfs(0, n−1) ≥ 0.

Step‑by‑Step Walkthrough

For nums = [1,5,2]:

1. dfs(0,2) considers picking 1 or 2.
2. If pick 1 → net = 1 − dfs(1,2). dfs(1,2) = max(5 − dfs(2,2), 2 − dfs(1,1)) = max(5−2, 2−5) = max(3, −3) = 3 → pickLeft path = 1−3 = −2.
3. If pick 2 → net = 2 − dfs(0,1). dfs(0,1) = max(1 − dfs(1,1), 5 − dfs(0,0)) = max(1−5, 5−1) = max(−4,4) = 4 → pickRight path = 2−4 = −2.
4. dfs(0,2) = max(−2,−2) = −2 < 0 → Player 1 loses.

Python Implementation