algoadvance

Leetcode 486. Predict the Winner

Problem Statement

You are given an integer array nums. Two players are playing a game with this array: Player 1 and Player 2. They take turns, with Player 1 starting first. Both players know the entire array and can choose either the first or the last element from the array to remove. After removing an element, the player’s score is increased by that element’s value, and the player loses that turn. The game ends when there are no more elements to remove, and the player with the higher score wins.

Implement a function to determine if Player 1 can win the game given they both play optimally.

Return true if Player 1 can win, otherwise return false.

Example 1:

Input: nums = [1, 5, 2]
Output: false
Explanation: Initially, Player 1 can choose between 1 and 2. If he chooses 2 (more optimal), then Player 2 has to choose between 1 and 5. If Player 2 chooses 5, then Player 1’s remaining choice will be 1; thus, by the end Player 2 has more score (5+1 > 2).

Example 2:

Input: nums = [1, 5, 233, 7]
Output: true
Explanation: Player 1 can choose 1, then Player 2 can choose 5, followed by Player 1 choosing 233, and finally Player 2 choosing 7. Player 1 wins with a total score of 234 (1 + 233) against Player 2's total score of 12 (5 + 7).

Clarifying Questions

  1. Can the length of the array be zero?
    • It’s assumed that the minimum length will be 1.
  2. Can the numbers be negative?
    • For simplicity, assume that the numbers are positive in this problem.
  3. What is the range of numbers in the array?
    • The numbers can range from 0 to (10^7) and the length of the array can be up to 20.

Strategy

This problem can be solved using Dynamic Programming and the Minimax algorithm, where we will create a recursive solution to simulate the optimal moves of both players.

  1. Define State: Use a 2D array dp where dp[i][j] represents the maximum score difference a player can achieve over their opponent if considering the subarray from index i to j.

  2. Recurrence Relation:
    • If i > j, return a score of 0 (base case when no elements are left).
    • When it’s a player’s turn, they can either pick the i-th or the j-th element. After their choice, it will be the opponent’s turn with an updated subarray.
    • We calculate the score difference if the player picks nums[i] and the score difference if the player picks nums[j].
  3. Base Case: When the subarray length is 1 (i.e., i == j), the score difference will be the value of that element.

Code

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

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

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

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

Time Complexity

The time complexity of the above solution is O(n²) because we fill an n x n DP table with results derived from overlapping subproblems. Each entry of dp[i][j] requires constant time operations.

Space Complexity

The space complexity is O(n²) due to the storage requirement of the dp array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI