Predict the Winner Solution in C++

Problem Description

Ah, the classic “Predict the Winner” problem! It’s like a game of poker, but instead of bluffing your way to victory, you’re just trying to outsmart your opponent with some good old-fashioned math. Imagine you and your friend are sitting at a table, surrounded by a pile of coins (or candy, if you prefer). You take turns picking coins from either end of the pile. The catch? You want to end up with more coins than your friend. Sounds simple, right? Well, it’s not just about grabbing the shiny coins; it’s about predicting what your friend will do next.

In this game, you need to determine if you can win given the coins in a line. If you can guarantee a win, you’re the champion! If not, well, better luck next time.

Code Solution

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

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

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
      }

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

Approach

The approach used in this solution is dynamic programming. We create a 2D array dp where dp[i][j] represents the maximum score difference you can achieve over your opponent when considering the subarray nums[i..j]. The idea is to fill this table by considering all possible subarrays and calculating the best possible outcome based on the choices available.

1. If you pick the leftmost coin, your opponent will then play optimally on the remaining coins.
2. If you pick the rightmost coin, the same logic applies.
3. The goal is to maximize your score while minimizing your opponent’s potential score.

Time and Space Complexity

Time Complexity: O(n²), where n is the number of coins. This is because we are filling a 2D array of size n x n.

Space Complexity: O(n²) as well, due to the storage of the dp array.

Real-World Example

Imagine you and your sibling are at a candy store, and you both want to grab the best candies from a line of jars. You can only take from either end of the line, and you want to ensure you end up with more candies than your sibling. You strategize, thinking, “If I take this jar, they’ll take that one, and then I can take the next best one.” This is exactly what the algorithm does—predicting the best moves to ensure victory!