Determine the Winner of a Bowling Game

Easy

DE Shaw

1 view

Topics:

Arrays

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 x_i pins in the i^th turn. The value of the i^th turn for the player is:

2x_i if the player hits 10 pins in either (i - 1)^th or (i - 2)^th turn.
Otherwise, it is x_i.

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

Determine the Winner of a Bowling Game

Easy

DE Shaw

1 view

Topics:

Arrays

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 x_i pins in the i^th turn. The value of the i^th turn for the player is:

2x_i if the player hits 10 pins in either (i - 1)^th or (i - 2)^th turn.
Otherwise, it is x_i.

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input arrays, player1 and player2?
Can the individual scores in player1 and player2 be negative or non-integer values?
If there are consecutive strikes, how does the bonus calculation work (e.g., strike followed by another strike)?
Is there a maximum possible score for each throw?
Is there a possibility of either player1 or player2 being null or empty?

Brute Force Solution

Approach

To find the bowling game winner, the brute force way means we will check every possible score to see who wins. It's like trying every single thing until we find the answer. We'll go through each player's points one by one and calculate scores based on all the bonus possibilities.

Here's how the algorithm would work step-by-step:

Start with the first player's scores.
Go through each frame, one at a time.
If the player gets a strike or spare, calculate the bonus points they would get for each possible following roll combination.
Add these bonus points to the current frame's score to get the frame total for each bonus possibility.
Keep a running total of the score for each frame and its bonus possibilities.
Repeat this process for all the players.
After calculating all the possible final scores for each player, compare them to see who has the highest score.
The player with the absolute highest score among all players and all their score variations wins.

Code Implementation

def determine_bowling_winner_brute_force(player_scores_list):
    highest_score = -1
    winning_player_index = -1

    for player_index, player_scores in enumerate(player_scores_list):
        possible_scores = calculate_possible_scores(player_scores)

        for score in possible_scores:
            if score > highest_score:
                highest_score = score
                winning_player_index = player_index

    return winning_player_index

def calculate_possible_scores(player_scores):
    possible_final_scores = set()
    calculate_frame_score(player_scores, 0, 0, [], possible_final_scores)
    return possible_final_scores

def calculate_frame_score(player_scores, frame_index, current_score, current_rolls, possible_final_scores):
    if frame_index == 10:
        possible_final_scores.add(current_score)
        return

    first_roll = player_scores[frame_index][0]
    second_roll = player_scores[frame_index][1]

    # Handle strike
    if first_roll == 10:
        # Need to consider bonus from next two rolls
        calculate_strike_bonus(player_scores, frame_index, current_score, current_rolls, possible_final_scores)
    # Handle spare
    elif first_roll + second_roll == 10:
        # Need to consider bonus from next roll
        calculate_spare_bonus(player_scores, frame_index, current_score, current_rolls, possible_final_scores)
    else:
        # Regular frame
        frame_score = first_roll + second_roll
        calculate_frame_score(player_scores, frame_index + 1, current_score + frame_score, current_rolls, possible_final_scores)

def calculate_strike_bonus(player_scores, frame_index, current_score, current_rolls, possible_final_scores):
    if frame_index < 9:

        next_frame_index = frame_index + 1
        first_next_roll = player_scores[next_frame_index][0]

        # If next frame is also a strike
        if first_next_roll == 10 and next_frame_index < 9:
            # Need to look at the frame after that to calculate bonus
            next_next_frame_index = next_frame_index + 1
            second_next_roll = player_scores[next_next_frame_index][0] if next_next_frame_index < 10 else 0
            frame_score = 10 + 10 + second_next_roll

            calculate_frame_score(player_scores, frame_index + 1, current_score + frame_score, current_rolls, possible_final_scores)
        else:
            # next frame is not a strike calculate based on two rolls
            second_next_roll = player_scores[next_frame_index][1]
            frame_score = 10 + first_next_roll + second_next_roll
            calculate_frame_score(player_scores, frame_index + 1, current_score + frame_score, current_rolls, possible_final_scores)
    else:
        # Handle strike in the 10th frame, bonus is from additional rolls
        frame_score = 10 + player_scores[frame_index][1] + player_scores[frame_index][2]
        calculate_frame_score(player_scores, frame_index + 1, current_score + frame_score, current_rolls, possible_final_scores)

def calculate_spare_bonus(player_scores, frame_index, current_score, current_rolls, possible_final_scores):
    if frame_index < 9:
        # Need to determine bonus from next roll
        next_frame_index = frame_index + 1
        first_next_roll = player_scores[next_frame_index][0]
        frame_score = 10 + first_next_roll
        calculate_frame_score(player_scores, frame_index + 1, current_score + frame_score, current_rolls, possible_final_scores)
    else:
        # Calculate 10th frame spare bonus
        frame_score = 10 + player_scores[frame_index][2]
        calculate_frame_score(player_scores, frame_index + 1, current_score + frame_score, current_rolls, possible_final_scores)

# Brute force means checking every combination, so it is very inefficient
# This is the starting point for going through scores one by one

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(k * b^s) – Let n be the number of players, k be the number of frames in a bowling game (typically 10), and s be the maximum number of subsequent rolls considered for bonus calculation (2 for a strike, 1 for a spare). For each player, and for each frame, the algorithm explores all possible bonus roll combinations. The number of such combinations 'b' is dependent on how many subsequent balls are used and what the value of each can be. Since there are 'k' frames, and each frame has a possible branching factor of approximately 'b' raised to the power of 's', we need to multiply it by the number of players involved. Thus we have n * k * b^s. Considering k as constant, and focusing on the number of players the time complexity becomes O(n * b^s). Typically, since we want to determine the winner of the bowling game, we assume n is small and focus on the number of possible outcomes. Therefore, considering only a single player for simplicity and ignoring k, the complexity simplifies to O(b^s).

Space Complexity

O(K * P * M) – The brute force algorithm calculates all possible scores for each player. The algorithm stores the running total of the score for each frame and its bonus possibilities. If there are K players, and for each player, there are P possible bonus combinations for each of the M frames, then the space complexity is O(K * P * M), because we are storing intermediate scores for each possibility of bonus points in each frame for each player. Assuming the number of bonus possibilities P is bounded and relatively small, we could simplify to O(K * M), but the prompt suggests we strictly adhere to the operations described in the plain english explanation and therefore we will include the P term.

Optimal Solution

Approach

The efficient way to find the bowling winner involves calculating each player's score, considering strike and spare bonuses. Instead of storing all intermediate scores, we update scores as we go, focusing on the relevant frames that earn bonuses.

Here's how the algorithm would work step-by-step:

Go through each player's rolls one frame at a time.
Calculate the base score for each frame (the sum of the rolls in that frame).
If a strike was bowled, add the next two rolls to the current frame's score. Be careful not to go beyond the end of the game.
If a spare was bowled, add the next single roll to the current frame's score. Again, be mindful of game's end.
Keep a running total for each player by adding each frame's score to their overall score.
After processing all frames for both players, compare their total scores to determine the winner.

Code Implementation

def determine_bowling_winner(player1_rolls, player2_rolls):
    player1_score = calculate_score(player1_rolls)
    player2_score = calculate_score(player2_rolls)

    if player1_score > player2_score:
        return 1
    elif player2_score > player1_score:
        return 2
    else:
        return 0

def calculate_score(rolls):
    total_score = 0
    frame_index = 0

    for frame_number in range(10):
        frame_score = rolls[frame_index] + rolls[frame_index + 1]

        # Handle strike bonus: add the next two rolls to frame_score
        if rolls[frame_index] == 10:
            frame_score = 10
            if frame_index + 2 < len(rolls):
                frame_score += rolls[frame_index + 1] + rolls[frame_index + 2]
            elif frame_index + 1 < len(rolls):
                frame_score += rolls[frame_index + 1]
            total_score += frame_score
            frame_index += 1

        # Handle spare bonus: add the next roll to frame_score
        elif rolls[frame_index] + rolls[frame_index + 1] == 10:
            if frame_index + 2 < len(rolls):
                frame_score += rolls[frame_index + 2]
            total_score += frame_score
            frame_index += 2

        else:
            total_score += frame_score
            frame_index += 2

    return total_score

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each player's rolls frame by frame. The number of frames in a bowling game is fixed (10 frames, with potentially up to 3 rolls in the last frame). Although strikes and spares require looking ahead at the next one or two rolls, the number of lookahead operations is constant (at most 2). Since the number of frames is constant and the lookahead operations are also constant, the time complexity depends linearly on the number of frames, n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm primarily uses a few variables to store the scores of each player and to iterate through the rolls. The space required for these variables remains constant irrespective of the number of rolls, N. No auxiliary data structures like arrays or hash maps that scale with the input size are used, therefore the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty player1 and player2 arrays	Return 0, representing a draw since both players have no score.
Null player1 or player2 arrays	Throw an IllegalArgumentException or return an error code indicating invalid input.
Arrays with only one element each (no strike possible)	Calculate the winner directly based on the single element value of each array.
Large arrays with many strikes, causing frequent score doubling	Ensure the score calculation loop handles numerous strike bonuses efficiently without exceeding time limits.
Consecutive strikes for a player	Ensure that the bonus calculation correctly handles the overlapping bonus windows from consecutive strikes.
Integer overflow when calculating the score with bonus	Use long data type to store player scores to prevent overflow, or check if intermediate value might overflow the integer before adding the bonus.
Arrays with different lengths	Process each array to its end, calculating bonuses based on its own throws.
Arrays containing only strikes	The bonus calculation logic should correctly handle arrays entirely composed of strikes, doubling the next two throws appropriately.