Scale Engineer

Determine the Winner of a Bowling Game

Easy
#2417Time: 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.1 company
Data structures
Array
Companies
DE Shaw

Prompt

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.
  • 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.length
  • 1 <= n <= 1000
  • 0 <= 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

  1. Define a helper function calculateScore(int[] pins).
  2. Inside calculateScore, initialize score = 0.
  3. Loop for i from 0 to pins.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. If bonus is true, add 2 * pins[i] to score. c. Otherwise, add pins[i] to score.
  4. Return the total score.
  5. In the main function, call this helper to get score1 = calculateScore(player1) and score2 = calculateScore(player2).
  6. Compare score1 and score2 and 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.

Solutions

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 ; } }

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.

← Previous

Previous problem

Next →

Next problem