Predict the Winner — Editorial

Opening the reading…

Intuitionwhy score difference is easier than tracking two totals

At any turn, only the numbers between indices i and j remain. Instead of storing both players' future totals, define the value of this interval as the largest score difference the player whose turn it is can achieve over the other player. A non-negative value means the player to move eventually ties or wins; a negative value means that player eventually loses.

If the player takes nums[i], the opponent becomes the player to move on i + 1 to j. That opponent can secure dfs(i + 1, j) more than the next player, so the current player's net result is nums[i] - dfs(i + 1, j). Taking the right end similarly gives nums[j] - dfs(i, j - 1). The current player chooses the larger result.

Approach

Create a memo table for every pair of interval endpoints, because the same remaining interval can be reached through different sequences of picks and should be solved only once.

Define dfs(i, j) as the best net score difference for the player whose turn it is when nums[i] through nums[j] remain, because this definition stays identical after either possible pick.

Return 0 when i > j, because an empty interval gives the player to move no numbers and provides the clean stopping value for the last pick.

Compute the left choice as nums[i] - dfs(i + 1, j), because taking nums[i] gives points now while the opponent's optimal difference on the remainder works against the current player.

Compute the right choice as nums[j] - dfs(i, j - 1) for the same reason, with the right endpoint removed instead of the left endpoint.

Store max(takeLeft, takeRight) in memo[i][j], because optimal play chooses the move that produces the better final difference and caching prevents exponential repeated recursion.

Evaluate dfs(0, n - 1) and return whether it is at least zero, because Player 1 starts and a zero difference counts as a win.

Complexitythe interval count determines both bounds

MEASURE	BOUND	WHY
Time	O(n^2)	There are n(n + 1) / 2 non-empty intervals, and each memoized interval evaluates exactly two endpoint choices once. Every later request returns in constant time, so no interval is recomputed.
Space	O(n^2)	The memo and seen tables reserve O(n^2) working memory, while the recursion stack adds O(n) and is dominated by the tables. The returned boolean is required output and is excluded. This bound is already the worst shape for the input because all endpoint pairs may be queried.

Here n is the number of values in nums. The memo table has one state for each pair of interval endpoints.

Annotated solutionC++ · top-down interval DP · the recurrence stays visible

CPPMemoized recursion that stores the best score difference for each remaining interval.

#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> memo(n, vector<int>(n, 0));
        vector<vector<bool>> seen(n, vector<bool>(n, false));

        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i > j) return 0;
            if (seen[i][j]) return memo[i][j];

            seen[i][j] = true;
            int takeLeft = nums[i] - dfs(i + 1, j);
            int takeRight = nums[j] - dfs(i, j - 1);
            memo[i][j] = max(takeLeft, takeRight);
            return memo[i][j];
        };

        return dfs(0, n - 1) >= 0;
    }
};

The subtraction in both choices is the central line of the solution. After the current player takes an endpoint, the opponent becomes the player to move on the smaller interval. Because dfs measures the advantage of whoever moves next, that future advantage belongs on the other side of the current player's score.

The bottom-up alternativethe same interval recurrence without runtime recursion

You can fill the intervals from short to long instead of asking recursion to discover them. An interval of length one has difference nums[i]. For a longer interval, both intervals on the right side of the recurrence are shorter by one, so their values are already available. This is a different arrangement, not an asymptotic optimisation: it keeps O(n^2) time and uses O(n^2) table space while removing the call stack.

CPPBottom-up interval DP filled by increasing subarray length.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; ++i) {
            dp[i][i] = nums[i];
        }

        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i + length <= n; ++i) {
                int j = i + length - 1;
                int takeLeft = nums[i] - dp[i + 1][j];
                int takeRight = nums[j] - dp[i][j - 1];
                dp[i][j] = max(takeLeft, takeRight);
            }
        }

        return dp[0][n - 1] >= 0;
    }
};