Predict the Winner

MEDIUM

Description

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

Example 1:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.

Example 2:

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 10⁷

Approaches

Checkout 4 different approaches to solve Predict the Winner. Click on different approaches to view the approach and algorithm in detail.

Space-Optimized Iterative Dynamic Programming

This approach optimizes the space complexity of the bottom-up DP solution. Observing the recurrence relation dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]), we see that to compute a row i of the DP table, we only need the values from the row i+1 and the previously computed values in the current row i. This dependency allows us to reduce the 2D DP table to a 1D array, bringing the space complexity down from O(n^2) to O(n).

Algorithm

Create a 1D DP array dp[n].
Iterate i from n - 1 down to 0.
Inside, iterate j from i to n - 1.
If i == j, set dp[i] = nums[i] (or dp[j] = nums[j] since i==j).
Otherwise, update dp[j] using the recurrence: dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1]).
After the loops, the result for the whole array is in dp[n-1].
Return dp[n-1] >= 0.

Instead of a 2D dp table, we use a 1D array, say dp[n]. We can iterate through the subproblems in a way that allows us to reuse this single array. The key is to iterate i from n-1 down to 0, and for each i, iterate j from i to n-1. In this setup, dp[j] will store the result for the subarray ending at j that starts at the current i. The update rule becomes dp[j] = max(nums[i] - dp[j], nums[j] - dp[j-1]). Let's trace the update for dp[j]:

nums[i] - dp[j]: Here, dp[j] still holds the value from the previous outer loop iteration (for i+1), which corresponds to dp[i+1][j] in the 2D version.
nums[j] - dp[j-1]: Here, dp[j-1] has already been updated in the current inner loop iteration, so it holds the value for dp[i][j-1]. This clever iteration order allows us to correctly compute all required values using only one array. The final answer, the score difference for the entire array nums[0...n-1], will be stored in dp[n-1] at the end of the process.

class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    dp[i] = nums[i];
                } else {
                    int scoreByTakingFirst = nums[i] - dp[j];
                    int scoreByTakingLast = nums[j] - dp[j - 1];
                    dp[j] = Math.max(scoreByTakingFirst, scoreByTakingLast);
                }
            }
        }

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

Complexity Analysis

Time Complexity: O(n^2), due to the nested loops.Space Complexity: O(n), for the 1D DP array.

Pros and Cons

Pros:

Most efficient approach in terms of space.
Maintains the efficient O(n^2) time complexity.

Cons:

The logic for the iteration order can be less intuitive to derive compared to the 2D DP approach.

Code Solutions

Checking out 3 solutions in different languages for Predict the Winner. Click on different languages to view the code.

class Solution {
public
  boolean PredictTheWinner(int[] nums) {
    int n = nums.length;
    int[][] f = new int[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][i] = nums[i];
    }
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = Math.max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1]);
      }
    }
    return f[0][n - 1] >= 0;
  }
}

Video Solution

Watch the video walkthrough for Predict the Winner

Patterns:

MathRecursionDynamic ProgrammingGame Theory

Data Structures:

Array

Companies:

Cisco |Flipkart |Salesforce |