DDSA Solutions

486. Predict the Winner

MediumView on LeetCode
ArrayMathDynamic ProgrammingGame Theory

Problem Overview

Two players alternately take from either end of nums, both playing optimally.

Intuition

Two players alternately take from either end of nums, both playing optimally. Player 1 wins if their score is at least Player 2. Track the score gap (picker minus opponent) on every subarray: picking an end leaves the opponent with the optimal gap on the remaining segment, so your gap is that end value minus the opponent gap.

Algorithm

  1. 1Clone nums into dp; for length-1 intervals the only pick is the element itself.
  2. 2For distance d = 1..n-1, for each right endpoint j with i = j - d:
  3. 3 dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]).
  4. 4Return true iff dp[n - 1] >= 0 (Player 1 difference on the full array is non-negative).

Example Walkthrough

Input: nums = [1, 5, 2]

  1. 1.Length 2: [1,5] -> max(1-5, 5-1) = 4; [5,2] -> max(5-2, 2-5) = 3.
  2. 2.Full [1,5,2]: max(1-3, 2-4) = max(-2, -2) = -2.
  3. 3.Difference < 0, so Player 1 cannot win under optimal play.

Output: false

Common Pitfalls

  • •The DP stores a signed difference, not Player 1 raw score alone.
  • •Process increasing interval lengths so smaller intervals are already finalized.
  • •A tie (difference 0) counts as a win for Player 1.
  • •In-place 1D DP overwrites carefully from the right for each d.
486.cs
C#
public class Solution
{
    // Approach: Minimax on a line of scores. dp[j] = best score difference
    // (current player minus opponent) on subarray ending at j. Expand length d:
    // for interval [i,j], take max of nums[i]-dp[j] (pick left) and nums[j]-dp[j-1]
    // (pick right). Player 1 wins if the full-array difference dp[n-1] >= 0.
    // Complexity: O(n^2) time and O(n) space.
    public bool PredictTheWinner(int[] nums)
    {
        int n = nums.Length;
        int[] dp = (int[])nums.Clone();

        for (int d = 1; d < n; ++d)
            for (int j = n - 1; j - d >= 0; --j)
            {
                int i = j - d;
                dp[j] = Math.Max(nums[i] - dp[j],      // Pick the leftmost number.
                                 nums[j] - dp[j - 1]); // Pick the rightmost number.
            }

        return dp[n - 1] >= 0;
    }
}
Was this solution helpful?

Related Problems