Determine the Winner of a Bowling Game
EasyPrompt
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:
2xiif the player hits 10 pins in either (i - 1)th or (i - 2)th turn.- Otherwise, it is
xi.
The score of the player is the sum of the values of their n turns.
Return
- 1 if the score of player 1 is more than the score of player 2,
- 2 if the score of player 2 is more than the score of player 1, and
- 0 in case of a draw.
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] <= 10
Approaches
2 approaches with complexity analysis and trade-offs.
This approach focuses on code clarity and reusability by creating a dedicated helper function, calculateScore. This function takes a player's pin array as input and returns their total score according to the game's rules. The main function then calls this helper for each player, compares the returned scores, and determines the winner. This modular design makes the code easy to read, test, and maintain.
Algorithm
- Define a helper function
calculateScore(int[] pins). - Inside
calculateScore, initializescore = 0. - Loop for
ifrom 0 topins.length - 1: a. Determine if a bonus applies by checking the previous two turns:bonus = (i > 0 && pins[i-1] == 10) || (i > 1 && pins[i-2] == 10). b. Ifbonusis true, add2 * pins[i]toscore. c. Otherwise, addpins[i]toscore. - Return the total
score. - In the main function, call this helper to get
score1 = calculateScore(player1)andscore2 = calculateScore(player2). - Compare
score1andscore2and return 1, 2, or 0 accordingly.
Walkthrough
The core logic is encapsulated in a calculateScore(int[] pins) method. This method initializes a score variable to 0 and iterates through the pins array from the first turn (i = 0) to the last. In each iteration i, it checks if the player scored a 10 in the previous turn (i-1) or the turn before that (i-2). Care is taken to handle the edge cases for the first two turns to avoid ArrayIndexOutOfBoundsException. If a 10 was scored in either of the two preceding turns, the current turn's value pins[i] is doubled; otherwise, it's taken as is. This value is added to the total score. After the loop, the total score is returned. The main isWinner function simply orchestrates the calls to calculateScore for both players and compares the results.
class Solution { public int isWinner(int[] player1, int[] player2) { int score1 = calculateScore(player1); int score2 = calculateScore(player2); if (score1 > score2) { return 1; } else if (score2 > score1) { return 2; } else { return 0; } } private int calculateScore(int[] pins) { int score = 0; int n = pins.length; for (int i = 0; i < n; i++) { boolean hasBonus = false; if (i > 0 && pins[i - 1] == 10) { hasBonus = true; } if (i > 1 && pins[i - 2] == 10) { hasBonus = true; } if (hasBonus) { score += 2 * pins[i]; } else { score += pins[i]; } } return score; }}Complexity
Time
O(n), where n is the number of turns. The `calculateScore` function iterates through the array once, taking O(n) time. It's called twice, resulting in a total time complexity of O(n) + O(n) = O(n).
Space
O(1). We only use a few variables to store the scores and loop counters, which does not scale with the input size.
Trade-offs
Pros
Clean and modular code, promoting reusability.
Follows the Don't Repeat Yourself (DRY) principle.
Easy to understand, test, and debug.
Cons
Incurs a minor overhead from function calls compared to an inlined, single-loop approach.
This approach optimizes the calculation by processing both players' scores within a single loop. Instead of using a separate helper function, we iterate from the first turn to the last, and in each iteration, we calculate and update the scores for both player 1 and player 2 simultaneously. This avoids the overhead of function calls and consolidates the logic into one place, making it slightly more performant.
Algorithm
- Initialize
score1 = 0andscore2 = 0. - Let
nbe the length of the player arrays. - Loop for
ifrom 0 ton - 1: a. Player 1: i. Check if(i > 0 && player1[i-1] == 10) || (i > 1 && player1[i-2] == 10). ii. If the condition is true, add2 * player1[i]toscore1. Otherwise, addplayer1[i]. b. Player 2: i. Check if(i > 0 && player2[i-1] == 10) || (i > 1 && player2[i-2] == 10). ii. If the condition is true, add2 * player2[i]toscore2. Otherwise, addplayer2[i]. - After the loop, compare
score1andscore2. - If
score1 > score2, return 1. - If
score2 > score1, return 2. - Otherwise, return 0.
Walkthrough
We initialize two variables, score1 and score2, to 0. Then, we iterate with an index i from 0 to n-1, where n is the number of turns. Inside the loop, for each turn i, we calculate the turn's value for both players. For player 1, we check if they had a strike in turn i-1 or i-2. If so, we add 2 * player1[i] to score1; otherwise, we add player1[i]. We perform the exact same calculation for player 2 and score2. After the single loop completes, both score1 and score2 will hold the final scores. Finally, we compare the two scores and return 1, 2, or 0 as required.
class Solution { public int isWinner(int[] player1, int[] player2) { int score1 = 0; int score2 = 0; int n = player1.length; for (int i = 0; i < n; i++) { // Calculate score for player 1 boolean bonus1 = (i > 0 && player1[i - 1] == 10) || (i > 1 && player1[i - 2] == 10); score1 += bonus1 ? 2 * player1[i] : player1[i]; // Calculate score for player 2 boolean bonus2 = (i > 0 && player2[i - 1] == 10) || (i > 1 && player2[i - 2] == 10); score2 += bonus2 ? 2 * player2[i] : player2[i]; } if (score1 > score2) { return 1; } else if (score2 > score1) { return 2; } else { return 0; } }}Complexity
Time
O(n), where n is the number of turns. We iterate through the arrays only once to calculate both scores.
Space
O(1). Constant extra space is used for the score variables and the loop index.
Trade-offs
Pros
Optimal time and space complexity.
Slightly more performant in practice by avoiding function call overhead.
Consolidates all logic into a single loop.
Cons
Repeats the scoring logic for both players, which violates the DRY (Don't Repeat Yourself) principle.
Can be slightly harder to maintain if the scoring rules were to change, as the logic would need to be updated in two places.
Solutions
Solution
class Solution { public int isWinner ( int [] player1 , int [] player2 ) { int a = f ( player1 ), b = f ( player2 ); return a > b ? 1 : b > a ? 2 : 0 ; } private int f ( int [] arr ) { int s = 0 ; for ( int i = 0 ; i < arr . length ; ++ i ) { int k = ( i > 0 && arr [ i - 1 ] == 10 ) || ( i > 1 && arr [ i - 2 ] == 10 ) ? 2 : 1 ; s += k * arr [ i ]; } return s ; } }class Solution { public: int isWinner ( vector < int >& player1 , vector < int >& player2 ) { auto f = []( vector < int >& arr ) { int s = 0 ; for ( int i = 0 , n = arr . size (); i < n ; ++ i ) { int k = ( i && arr [ i - 1 ] == 10 ) || ( i > 1 && arr [ i - 2 ] == 10 ) ? 2 : 1 ; s += k * arr [ i ]; } return s ; }; int a = f ( player1 ), b = f ( player2 ); return a > b ? 1 : ( b > a ? 2 : 0 ); } };class Solution : def isWinner ( self , player1 : List [ int ], player2 : List [ int ]) -> int : def f ( arr : List [ int ]) -> int : s = 0 for i , x in enumerate ( arr ): k = 2 if ( i and arr [ i - 1 ] == 10 ) or ( i > 1 and arr [ i - 2 ] == 10 ) else 1 s += k * x return s a , b = f ( player1 ), f ( player2 ) return 1 if a > b else ( 2 if b > a else 0 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.