Predict the Winner

The problem. Two players take turns removing one number from either end of the array nums, adding it to their own score. Player 1 goes first, and both play as well as possible. Return true if Player 1 can win or tie.

Example

nums = [1, 5, 2]       ->  false   (Player 2 always gets the 5)
nums = [1, 5, 233, 7]  ->  true    (take 1; whatever Player 2 takes, 233 is reachable)
nums = [7]             ->  true

The idea: the best lead over the other player

Define lead(l, r) = the most the player about to move can end up ahead by, playing on nums[l..r]. If they take nums[l], the opponent then moves on nums[l+1..r] and gets a lead of lead(l + 1, r) over them — so their lead is nums[l] − lead(l + 1, r). Taking nums[r] works the same way. They pick the better: lead(l, r) = max(nums[l] − lead(l+1, r), nums[r] − lead(l, r−1)). With one number left, the lead is that number. Player 1 wins or ties when lead(0, n−1) >= 0. Thinking in leads means one function serves both players.

1. Plain recursion

1function predictTheWinner(nums) {2  const lead = (l, r) => {                       // best lead for whoever moves on nums[l..r]3    if (l === r) return nums[l];                 // one number left: take it4    const takeLeft = nums[l] - lead(l + 1, r);   // the opponent then leads by lead(l+1, r)5    const takeRight = nums[r] - lead(l, r - 1);6    return Math.max(takeLeft, takeRight);7  };8  return lead(0, nums.length - 1) >= 0;9}

Time O(2ⁿ), space O(n). Every call branches twice. With n up to 20, that's about a million calls — acceptable here, but the same ranges are solved many times.

2. Remember each range

There are only n² different ranges (l, r). Store each lead the first time — top-down dynamic programming.

1function predictTheWinner(nums) {2  const n = nums.length;3  const memo = Array.from({ length: n }, () => new Array(n).fill(null));4  const lead = (l, r) => {5    if (l === r) return nums[l];6    if (memo[l][r] !== null) return memo[l][r];  // this range was solved before7    memo[l][r] = Math.max(nums[l] - lead(l + 1, r), nums[r] - lead(l, r - 1));8    return memo[l][r];9  };10  return lead(0, n - 1) >= 0;11}

Time O(n²), space O(n²). A bottom-up table filled by range length reaches the same time with O(n) memory — the interval pattern in the Dynamic Programming course.

Comparing the approaches

Edge cases to test

Variations