Determine the Winner of a Bowling Game

Difficulty: Easy | Acceptance: 37.50% | Paid: No Topics: Array, Simulation

You are given two integer arrays player1 and player2, representing the number of pins knocked down in each throw for two players in a bowling game.

The game consists of n turns, and the number of pins knocked down in the i-th turn for each player is player1[i] and player2[i] respectively.

The score of a player is the sum of the pins knocked down in all of their turns, but there is a special rule: If a player knocks down all 10 pins on the i-th turn (i.e., playerX[i] == 10), the score for the i+1-th and i+2-th turns is doubled. The doubled score is added to the player’s total score.

Note that the i+1-th and i+2-th turns might be outside the bounds of the array, in which case the doubling does not apply.

Return 1 if the score of player1 is higher than the score of player2, otherwise return 2. If the scores are equal, return 0.

• Examples
• Constraints
• Approach 1: Simulation with Helper Function
• Approach 2: State Tracking

Examples

Example 1

Input:

player1 = [5,10,3,2], player2 = [6,5,7,3]

Output:

1

Explanation: The score of player 1 is 5 + 10 + 23 + 22 = 25.

The score of player 2 is 6 + 5 + 7 + 3 = 21.

Example 2

Input:

player1 = [3,5,7,6], player2 = [8,10,10,2]

Output:

2

Explanation: The score of player 1 is 3 + 5 + 7 + 6 = 21.

The score of player 2 is 8 + 10 + 210 + 22 = 42.

Example 3

Input:

player1 = [2,3], player2 = [4,1]

Output:

0

Explanation: The score of player1 is 2 + 3 = 5.

The score of player2 is 4 + 1 = 5.

Example 4

Input:

player1 = [1,1,1,10,10,10,10], player2 = [10,10,10,10,1,1,1]

Output:

2

Explanation: The score of player1 is 1 + 1 + 1 + 10 + 210 + 210 + 2*10 = 73.

The score of player2 is 10 + 210 + 210 + 210 + 21 + 2*1 + 1 = 75.

Constraints

n == player1.length == player2.length
1 <= n <= 1000
0 <= player1[i], player2[i] <= 10

Approach 1: Simulation with Helper Function

Intuition We can simulate the game by iterating through the throws for each player. For every throw, we check if the previous one or two throws resulted in a strike (10 pins). If so, we double the current score; otherwise, we add it normally.

Steps

• Create a helper function calculateScore that takes an array of throws.
• Initialize a total score variable to 0.
• Loop through the array with index i.
• Check if i > 0 and arr[i-1] == 10, or if i > 1 and arr[i-2] == 10.
• If either condition is true, add 2 * arr[i] to the total.
• Otherwise, add arr[i] to the total.
• Call this helper for player1 and player2.
• Compare the results and return 1, 2, or 0.

class Solution:
    def isWinner(self, player1: list[int], player2: list[int]) -> int:
        def calculate_score(arr):
            total = 0
            for i in range(len(arr)):
                if (i > 0 and arr[i-1] == 10) or (i > 1 and arr[i-2] == 10):
                    total += 2 * arr[i]
                else:
                    total += arr[i]
            return total
        
        score1 = calculate_score(player1)
        score2 = calculate_score(player2)
        
        if score1 > score2:
            return 1
        elif score2 > score1:
            return 2
        else:
            return 0

Complexity

• Time: O(n) where n is the length of the player arrays. We iterate through the array once for each player.
• Space: O(1) extra space, excluding the input arrays.
• Notes: This approach is straightforward and easy to understand.

Approach 2: State Tracking

Intuition Instead of looking back at previous indices, we can maintain a counter that tracks how many subsequent throws should be doubled. If a player hits 10 pins, we set this counter to 2. We decrement the counter after each throw.

Steps

• Define a helper function getScore that takes an array.
• Initialize total to 0 and double to 0.
• Iterate through each pin count x in the array.
• If double > 0, add 2 * x to total and decrement double.
• Otherwise, add x to total.
• If x == 10, set double to 2 (since the next two throws are doubled).
• Compare the final scores for both players.

class Solution:
    def isWinner(self, player1: list[int], player2: list[int]) -> int:
        def get_score(arr):
            total = 0
            double = 0
            for x in arr:
                if double > 0:
                    total += 2 * x
                    double -= 1
                else:
                    total += x
                if x == 10:
                    double = 2
            return total
        
        s1 = get_score(player1)
        s2 = get_score(player2)
        
        if s1 > s2:
            return 1
        elif s2 > s1:
            return 2
        else:
            return 0

Complexity

• Time: O(n) where n is the length of the player arrays.
• Space: O(1) extra space.
• Notes: This approach avoids checking previous indices explicitly by maintaining state, which can be slightly more efficient in practice.