Scale Engineer

Predict the Winner

Med
#0473Time: O(n^2), due to the nested loops.Space: O(n), for the 1D DP array.3 companies
Patterns
MathRecursionDynamic ProgrammingGame Theory
Data structures
Array
Companies
CiscoFlipkartSalesforce

Prompt

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] <= 107

Approaches

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(n^2), due to the nested loops.

Space

O(n), for the 1D DP array.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem