LeetCode 2660 - Determine the Winner of a Bowling Game

The problem describes a simplified scoring system for a bowling game between two players. Each player has an array representing the number of pins hit in each turn, and there are exactly n turns.

leetcodeeasyarraysimulation

LeetCode Problem 2660

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

The problem describes a simplified scoring system for a bowling game between two players. Each player has an array representing the number of pins hit in each turn, and there are exactly n turns. Each turn normally scores the number of pins hit, but a bonus rule applies: if the player scored a strike (10 pins) in either of the two previous turns, the current turn’s score is doubled. The task is to compute the total score for both players according to these rules and determine the winner: player 1, player 2, or a draw if the scores are equal.

The input arrays are guaranteed to have the same length, up to 1000 elements, and each element is between 0 and 10. The constraints ensure the input is small enough to allow a straightforward simulation of the scoring rules without performance concerns. Key edge cases include short arrays (length 1 or 2), sequences of consecutive strikes, or draws.

Approaches

A brute-force approach would simulate the game exactly as described. For each turn, you check the previous two turns for strikes and compute the score accordingly. This is feasible for the given constraints since n is at most 1000. There is no need for a more complex optimization because each turn can be evaluated independently with only the previous two results affecting the score.

The key insight is that you only need to remember the scores of the previous two turns to decide if the current turn is doubled. This allows a simple single-pass algorithm for each player that sums up the total score using constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force / Simulation O(n) O(1) Iterate over each turn and apply bonus rules based on the previous two turns. Optimal for this problem size.

Algorithm Walkthrough

  1. Initialize score1 and score2 to 0. These will store the cumulative scores for player 1 and player 2.
  2. Loop over each turn index i from 0 to n-1.
  3. For each player, check the previous two turns. If either of them was a strike (10 pins), double the current turn’s pins; otherwise, use the normal pin count.
  4. Add the resulting value to the respective player’s cumulative score.
  5. After processing all turns, compare score1 and score2. Return 1 if score1 is greater, 2 if score2 is greater, or 0 if they are equal.

Why it works: The algorithm maintains the invariant that score always contains the correct sum of turn values according to the doubling rules. By checking only the last two turns, it correctly applies the bonus rules without storing unnecessary data.

Python Solution

from typing import List

class Solution:
    def isWinner(self, player1: List[int], player2: List[int]) -> int:
        def total_score(player: List[int]) -> int:
            score = 0
            for i in range(len(player)):
                if (i >= 1 and player[i-1] == 10) or (i >= 2 and player[i-2] == 10):
                    score += 2 * player[i]
                else:
                    score += player[i]
            return score

        score1 = total_score(player1)
        score2 = total_score(player2)

        if score1 > score2:
            return 1
        elif score2 > score1:
            return 2
        else:
            return 0

This Python implementation defines a helper function total_score that calculates a player's total score using a single pass. The conditional checks ensure the doubling rule is correctly applied based on the previous two turns.

Go Solution

func isWinner(player1 []int, player2 []int) int {
    totalScore := func(player []int) int {
        score := 0
        for i := 0; i < len(player); i++ {
            if (i >= 1 && player[i-1] == 10) || (i >= 2 && player[i-2] == 10) {
                score += 2 * player[i]
            } else {
                score += player[i]
            }
        }
        return score
    }

    score1 := totalScore(player1)
    score2 := totalScore(player2)

    if score1 > score2 {
        return 1
    } else if score2 > score1 {
        return 2
    } else {
        return 0
    }
}

The Go implementation mirrors the Python logic closely. The helper function totalScore is used to compute the total score for each player. Go handles integer arithmetic natively, and slices are used in place of lists.

Worked Examples

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

Turn P1 pins P1 score P2 pins P2 score
0 5 5 6 6
1 10 15 5 11
2 3 21 (2*3 because previous 10) 7 18
3 2 25 (2*2 because previous 3 was not 10, but two-turns-back was 10) 3 21

Winner: player 1

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

Turn P1 score P2 score
0 3 8
1 8 18
2 15 38 (2*10)
3 21 42 (2*2)

Winner: player 2

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through each player's turns once, applying a constant-time rule.
Space O(1) Only constant extra variables are used for scores; no additional arrays are required.

The time complexity is linear because we must check each turn once. The space complexity is constant as we do not store per-turn scores separately, just running totals.

Test Cases

# Provided examples
assert Solution().isWinner([5,10,3,2], [6,5,7,3]) == 1  # P1 wins
assert Solution().isWinner([3,5,7,6], [8,10,10,2]) == 2  # P2 wins
assert Solution().isWinner([2,3], [4,1]) == 0  # Draw
assert Solution().isWinner([1,1,1,10,10,10,10], [10,10,10,10,1,1,1]) == 2  # P2 wins

# Edge cases
assert Solution().isWinner([10], [10]) == 0  # Single turn, draw
assert Solution().isWinner([10,10], [10,9]) == 1  # P1 wins due to bonus
assert Solution().isWinner([0,0,10], [0,10,0]) == 2  # P2 wins due to bonus
assert Solution().isWinner([0]*1000, [0]*1000) == 0  # Large input, all zeros
Test Why
Single turn draw Validates minimal input size
Consecutive strikes Checks bonus application logic
Bonus on last turn Ensures correct doubling for turn n-1 and n-2
Large input all zeros Confirms efficiency for maximal input

Edge Cases

  1. Single-turn games: With only one element, the doubling condition cannot apply since there are no previous turns. The implementation correctly handles this by only checking indices 1 and 2.
  2. Consecutive strikes: If there are multiple 10s in a row, each subsequent turn may be doubled multiple times due to the previous two strikes. The algorithm correctly checks both i-1 and i-2 to ensure all applicable doublings are applied.
  3. Draws: Both players could have equal total scores even with different sequences of strikes and regular hits. The final comparison ensures that draws return 0, preventing incorrect winner assignment.