Stone Game Vi - Leetcode Solution

Problem Statement:

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player's turn, they can remove a stone from the pile and receive points based on the stone's value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally.

Determine the result (0, 1, or 2) of the game: 0 if Alice wins, 1 if Bob wins, or 2 if the game results in a draw.

Solution:

To solve this problem first we need to understand the given problem statement. We are given with two arrays, aliceValues, and bobValues, which contain the values that Alice and Bob will assign to each corresponding stone in the pile. Each player can select a stone from the pile whose value is greater than the other player's selected stone and adds it to his/her score. The game plays until all the stones are gone. The player who has the maximum score is the winner, if both players have equal scores then the game will end in a draw.

We can solve this problem using the greedy approach, where we select stones optimally. We start by sorting the stones according to their sum and then select stones alternately. Then we calculate the total score of both players at the end and compare them to find the winner.

Let's look at the detailed implementation of the algorithm:

• Initialize a variable, say result, to 0, which will store the index of the winning player.
• Define a list, say stones, that stores the sum of aliceValues[i] and bobValues[i] for each stone.
• Sort the stones in non-decreasing order.
• Initialize two variables, say aliceScore and bobScore, to 0, which store the total score of Alice and Bob, respectively.
• Loop over the sorted stones from the end to the beginning, and for each stone, do the following:
  • If the iteration index is even, add the corresponding aliceValues[i] to aliceScore; otherwise, add the corresponding bobValues[i] to bobScore.
• Compare aliceScore and bobScore to find the winner. If they are equal, set result to 2 (draw); otherwise, if aliceScore is greater than bobScore, set result to 0 (Alice wins); otherwise, set result to 1 (Bob wins).
• Return the result.

Code:

Here is the Python code for the Stone Game VI problem:

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        stones = [(aliceValues[i] + bobValues[i], i) for i in range(len(aliceValues))]
        stones.sort(reverse=True)
        aliceScore = 0
        bobScore = 0
        for i in range(len(aliceValues)):
            if i % 2 == 0:
                aliceScore += aliceValues[stones[i][1]]
            else:
                bobScore += bobValues[stones[i][1]]
        if aliceScore == bobScore:
            return 2
        elif aliceScore > bobScore:
            return 0
        else:
            return 1

Complexity Analysis:

The time complexity of this algorithm is O(nlogn), where n is the length of the arrays aliceValues and bobValues. Sorting stones takes O(nlogn) time, and iterating over sorted stones takes O(n) time. The space complexity is O(n) to store the list of stones.

1