Problem Description

You are given an array of integers called nums, where each element represents a score. Two players take turns picking either the first or last element from the array. Each picked number is added to that player's total score, and the element is removed from the array. The game continues until no elements remain.

Both players play optimally, meaning they always make the move that maximizes their own score. The goal is to determine whether the first player can win or at least tie (i.e., get a score greater than or equal to the second player's score), assuming both play perfectly.

Constraints:

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

Thought Process

At first glance, this problem looks like a simple greedy game: always pick the larger of the two ends. However, if both players do this, sometimes the second player can force a win by making the first player pick into a bad situation. So, a greedy approach is not guaranteed to work.

We need to consider every possible move, and for each move, the opponent will also play optimally. This is a classic example of a two-player minimax game, where each player tries to maximize their own score while minimizing the opponent's score.

The brute-force way would be to simulate every possible sequence of picks, but this would be very slow as the number of possibilities grows exponentially with the size of nums. To optimize, we can use recursion with memoization (dynamic programming) to avoid recalculating the same scenarios.

Solution Approach

Let's break down the solution step-by-step:

1. Define the State:
   • We use two pointers, left and right, to represent the current subarray of nums still in play.
   • The state is defined by the current range [left, right].
2. Recursive Relation:
   • At each turn, the player can pick either nums[left] or nums[right].
   • After picking, it's the opponent's turn, and they will also play optimally.
   • We compute the "score difference": the current player's score minus the opponent's score, for the current subarray.
   • The recursive formula is:
     • If the player picks nums[left], their score difference is nums[left] - score_diff(left+1, right).
     • If the player picks nums[right], their score difference is nums[right] - score_diff(left, right-1).
     • The player chooses the option with the maximum score difference.
3. Base Case:
   • If left == right, there's only one number left, so the current player takes it: nums[left].
4. Memoization:
   • Since the same subarray can be reached by different paths, we use a memoization table to store results for each (left, right) pair.
5. Final Decision:
   • After computing the score difference for the full array, if it is greater than or equal to 0, the first player can win or tie.

Example Walkthrough

Let's consider nums = [1, 5, 2].

1. First player's options:
   • Pick 1: Remaining array is [5, 2].
   • Pick 2: Remaining array is [1, 5].
2. Option 1: Pick 1
   • Second player chooses between 5 and 2.
   • If second picks 5: First gets 2, totals are First: 1+2=3, Second: 5.
   • If second picks 2: First gets 5, totals are First: 1+5=6, Second: 2.
   • Second player will pick 5 to maximize their score, so First ends with 3, Second with 5.
3. Option 2: Pick 2
   • Second player chooses between 1 and 5.
   • If second picks 1: First gets 5, totals are First: 2+5=7, Second: 1.
   • If second picks 5: First gets 1, totals are First: 2+1=3, Second: 5.
   • Second player will pick 5, so First ends with 3, Second with 5.
4. Both options lead to First player losing.
5. So the answer is False: First player cannot win.

Time and Space Complexity

• Brute-force Approach:
  • Each turn has two choices, and there are n numbers, so the time complexity is O(2^n).
  • Space complexity is O(n) for the recursion stack.
• Optimized DP Approach:
  • There are O(n^2) possible subarrays, and each is computed once due to memoization.
  • Each computation is O(1), so total time complexity is O(n^2).
  • Space complexity is O(n^2) for the memoization table.

Summary

This problem is a classic example of recursive minimax with memoization. By modeling the game as a score difference between the current player and the opponent, and memoizing intermediate results, we efficiently determine if the first player can win or tie. The dynamic programming approach reduces the exponential brute-force complexity to polynomial time, making it both elegant and efficient.

Code Implementation

class Solution:
    def PredictTheWinner(self, nums):
        from functools import lru_cache
        n = len(nums)
        
        @lru_cache(maxsize=None)
        def dp(left, right):
            if left == right:
                return nums[left]
            pick_left = nums[left] - dp(left + 1, right)
            pick_right = nums[right] - dp(left, right - 1)
            return max(pick_left, pick_right)
        
        return dp(0, n - 1) >= 0
      

class Solution {
public:
    int dp(int left, int right, vector<int>& nums, vector<vector<int>>& memo) {
        if (left == right) return nums[left];
        if (memo[left][right] != INT_MIN) return memo[left][right];
        int pickLeft = nums[left] - dp(left + 1, right, nums, memo);
        int pickRight = nums[right] - dp(left, right - 1, nums, memo);
        memo[left][right] = max(pickLeft, pickRight);
        return memo[left][right];
    }
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> memo(n, vector<int>(n, INT_MIN));
        return dp(0, n - 1, nums, memo) >= 0;
    }
};
      

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        Integer[][] memo = new Integer[n][n];
        return dp(nums, 0, n - 1, memo) >= 0;
    }
    
    private int dp(int[] nums, int left, int right, Integer[][] memo) {
        if (left == right) return nums[left];
        if (memo[left][right] != null) return memo[left][right];
        int pickLeft = nums[left] - dp(nums, left + 1, right, memo);
        int pickRight = nums[right] - dp(nums, left, right - 1, memo);
        memo[left][right] = Math.max(pickLeft, pickRight);
        return memo[left][right];
    }
}
      

var PredictTheWinner = function(nums) {
    const n = nums.length;
    const memo = Array.from({length: n}, () => Array(n).fill(null));
    
    function dp(left, right) {
        if (left === right) return nums[left];
        if (memo[left][right] !== null) return memo[left][right];
        const pickLeft = nums[left] - dp(left + 1, right);
        const pickRight = nums[right] - dp(left, right - 1);
        memo[left][right] = Math.max(pickLeft, pickRight);
        return memo[left][right];
    }
    
    return dp(0, n - 1) >= 0;
};