You are given two 0-indexed integer arrays player1 and player2, representing the number of pins that player 1 and player 2 hit in a bowling game, respectively.
The bowling game consists of n turns, and the number of pins in each turn is exactly 10.
Assume a player hits xi pins in the ith turn. The value of the ith turn for the player is:
2xi if the player hits 10 pins in either (i - 1)th or (i - 2)th turn.xi.The score of the player is the sum of the values of their n turns.
Return
Example 1:
Input: player1 = [5,10,3,2], player2 = [6,5,7,3]
Output: 1
Explanation:
The score of player 1 is 5 + 10 + 2*3 + 2*2 = 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 + 2*10 + 2*2 = 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 + 2*10 + 2*10 + 2*10 = 73.
The score of player2 is 10 + 2*10 + 2*10 + 2*10 + 2*1 + 2*1 + 1 = 75.
Constraints:
n == player1.length == player2.length1 <= n <= 10000 <= player1[i], player2[i] <= 10Problem Overview: You are given two arrays representing the pins knocked down by two bowling players in each round. A roll scores double if the player knocked down all 10 pins in either of the previous two rounds. Compute each player's total score and return the winner.
Approach 1: Simple Iterative Calculation (O(n) time, O(1) space)
This method directly simulates the scoring rule while iterating through the array. For every roll i, check whether either i-1 or i-2 equals 10. If so, the current roll contributes 2 * pins[i]; otherwise it contributes pins[i]. Accumulate the score in a running total. The same logic runs for both players and the final totals determine the winner.
The key insight is that the bonus rule depends only on the previous two rolls. No extra data structures are required, just boundary checks during iteration. This makes the solution extremely efficient and easy to implement. Problems like this are classic Array traversal combined with straightforward Simulation of rules.
Approach 2: Precompute Doubles (O(n) time, O(n) space)
Instead of checking the previous two rolls every time, precompute whether each index should receive a doubling bonus. Maintain a helper array or boolean flag indicating if the current roll is within the two-roll window after a strike. When a roll equals 10, mark the next two positions as doubled. During the final pass, compute the score using the precomputed flags.
This separates rule processing from score calculation, which some developers find cleaner when the scoring logic grows more complex. It trades constant memory for clarity, since the bonus information is stored explicitly. The algorithm still performs a single linear scan, keeping the time complexity at O(n).
Recommended for interviews: The simple iterative calculation is what interviewers usually expect. It demonstrates that you can translate a rule-based scoring system into efficient code using a single pass. Implementing the precompute approach shows the same understanding but uses more memory. Start with the direct simulation since it is shorter, clearer, and runs in O(n) time with O(1) space.
This approach involves iterating through the array of scores for each player, calculating the score for each turn while checking the previous two turn scores. If any of the last two turns resulted in 10 pins, the score for the current turn is doubled. We maintain a running total of scores.
In this Python solution, we define a helper function calculate_score that calculates the total score of a player based on the rules described. We check the scores in the previous two indices. If any of them is 10, we double the current score. Finally, we compare the total scores of both players to determine the winner.
Time Complexity: O(n), where n is the length of the player score array.
Space Complexity: O(1), as we only use a fixed amount of extra space.
In this approach, we first precompute an array indicating whether each turn's score should be doubled. This separates the logic of scoring from the main loop, potentially making the implementation more readable.
In this Java solution, we first determine which turns will have their scores doubled in a separate boolean array isDouble. Using this information, we determine the actual score for each player. This slightly separates the logic into computing isDouble values first, which may improve code readability.
Java
JavaScript
Time Complexity: O(n), where n is the length of the player score array.
Space Complexity: O(n), due to the extra storage required for the isDouble array.
| Approach | Complexity |
|---|---|
| Simple Iterative Calculation | Time Complexity: O(n), where n is the length of the player score array. |
| Precompute Doubles | Time Complexity: O(n), where n is the length of the player score array. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iterative Calculation | O(n) | O(1) | Best general solution. Minimal memory and straightforward rule simulation. |
| Precompute Doubles | O(n) | O(n) | Useful when separating rule tracking from scoring logic for readability or extension. |
6341. Determine the Winner of a Bowling Game | Leetcode Weekly Contest 343 | Pseudo Code. • Optimization • 891 views views
Watch 7 more video solutions →Practice Determine the Winner of a Bowling Game with our built-in code editor and test cases.
Practice on FleetCode