Find The First Player to win K Games in a Row

Medium

IBM

0 views

Topics:

Arrays

A competition consists of n players numbered from 0 to n - 1.

You are given an integer array skills of size n and a positive integer k, where skills[i] is the skill level of player i. All integers in skills are unique.

All players are standing in a queue in order from player 0 to player n - 1.

The competition process is as follows:

The first two players in the queue play a game, and the player with the higher skill level wins.
After the game, the winner stays at the beginning of the queue, and the loser goes to the end of it.

The winner of the competition is the first player who wins k games in a row.

Return the initial index of the winning player.

Example 1:

Input: skills = [4,2,6,3,9], k = 2

Output: 2

Explanation:

Initially, the queue of players is [0,1,2,3,4]. The following process happens:

Players 0 and 1 play a game, since the skill of player 0 is higher than that of player 1, player 0 wins. The resulting queue is [0,2,3,4,1].
Players 0 and 2 play a game, since the skill of player 2 is higher than that of player 0, player 2 wins. The resulting queue is [2,3,4,1,0].
Players 2 and 3 play a game, since the skill of player 2 is higher than that of player 3, player 2 wins. The resulting queue is [2,4,1,0,3].

Player 2 won k = 2 games in a row, so the winner is player 2.

Example 2:

Input: skills = [2,5,4], k = 3

Output: 1

Explanation:

Initially, the queue of players is [0,1,2]. The following process happens:

Players 0 and 1 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is [1,2,0].
Players 1 and 2 play a game, since the skill of player 1 is higher than that of player 2, player 1 wins. The resulting queue is [1,0,2].
Players 1 and 0 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is [1,2,0].

Player 1 won k = 3 games in a row, so the winner is player 1.

Constraints:

n == skills.length
2 <= n <= 10⁵
1 <= k <= 10⁹
1 <= skills[i] <= 10⁶
All integers in skills are unique.

Try coding it in LeetCode

Find The First Player to win K Games in a Row

Medium

IBM

0 views

Topics:

Arrays

A competition consists of n players numbered from 0 to n - 1.

You are given an integer array skills of size n and a positive integer k, where skills[i] is the skill level of player i. All integers in skills are unique.

All players are standing in a queue in order from player 0 to player n - 1.

The competition process is as follows:

The first two players in the queue play a game, and the player with the higher skill level wins.
After the game, the winner stays at the beginning of the queue, and the loser goes to the end of it.

The winner of the competition is the first player who wins k games in a row.

Return the initial index of the winning player.

Example 1:

Input: skills = [4,2,6,3,9], k = 2

Output: 2

Explanation:

Initially, the queue of players is [0,1,2,3,4]. The following process happens:

Players 0 and 1 play a game, since the skill of player 0 is higher than that of player 1, player 0 wins. The resulting queue is [0,2,3,4,1].
Players 0 and 2 play a game, since the skill of player 2 is higher than that of player 0, player 2 wins. The resulting queue is [2,3,4,1,0].
Players 2 and 3 play a game, since the skill of player 2 is higher than that of player 3, player 2 wins. The resulting queue is [2,4,1,0,3].

Player 2 won k = 2 games in a row, so the winner is player 2.

Example 2:

Input: skills = [2,5,4], k = 3

Output: 1

Explanation:

Initially, the queue of players is [0,1,2]. The following process happens:

Players 0 and 1 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is [1,2,0].
Players 1 and 2 play a game, since the skill of player 1 is higher than that of player 2, player 1 wins. The resulting queue is [1,0,2].
Players 1 and 0 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is [1,2,0].

Player 1 won k = 3 games in a row, so the winner is player 1.

Constraints:

n == skills.length
2 <= n <= 10⁵
1 <= k <= 10⁹
1 <= skills[i] <= 10⁶
All integers in skills are unique.

Try coding it in LeetCode

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 `n` and `k`, especially the maximum size of the `wins` array and the maximum value of `k`?
Can `k` be greater than `n` (the length of the `wins` array), or equal to 0, or negative?
What should I return if the `wins` array is empty?
Is the `wins` array guaranteed to only contain 1s and 2s, or could it contain other values?
If both players achieve `k` consecutive wins simultaneously, should I return the first player to *start* their winning streak, or is that impossible?

Brute Force Solution

Approach

The brute force approach is all about trying every single possibility to see which one works. In this game scenario, it means checking every possible sequence of games to see if either player wins K games in a row. We examine each potential starting point and consecutive sequence length.

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

Start by considering the first game in the sequence as the beginning of a potential winning streak.
Check if player 1 won that game, and if so, check if they also won the next K-1 games.
If player 1 did win K games in a row starting from that first game, we found our winner and we are done.
If not, repeat the process starting from the second game in the sequence.
This time, check if player 1 or player 2 won that game, and if so, check if that player also won the next K-1 games.
Keep doing this for every game in the sequence, always checking if starting at that game, either player won K games in a row.
If we go through the entire sequence without finding a winner, there is no winner.

Code Implementation

def find_first_winner(game_results, consecutive_wins_needed):
    number_of_games = len(game_results)

    for starting_game_index in range(number_of_games):
        winning_player = game_results[starting_game_index]
        current_streak_length = 1

        # Check for consecutive wins starting from the current game

        for next_game_index in range(starting_game_index + 1, number_of_games):
            if game_results[next_game_index] == winning_player:
                current_streak_length += 1
            else:
                break

            # If the streak reaches the required length, we found the winner
            if current_streak_length == consecutive_wins_needed:
                return winning_player

    # If no player reached the required consecutive wins
    return None

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through the array of n games. For each game, it checks if a player has won k consecutive games starting from that position. Therefore, in the worst case, for each of the n positions, we perform k comparisons to check for a winning streak. This leads to a time complexity of O(n*k), where n is the number of games and k is the number of consecutive wins needed.

Space Complexity

O(1) – The provided algorithm iterates through the input sequence, checking for winning streaks. It doesn't use any auxiliary data structures like lists, hash maps, or stacks to store intermediate results or track visited games. The algorithm uses a fixed number of variables to keep track of the current position and potentially the winning player, regardless of the input size N (the number of games). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The problem involves determining which player wins a series of games by being the first to achieve a specific number of consecutive wins. The optimal approach focuses on tracking consecutive wins efficiently and checking if either player reaches the winning condition in each step.

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

Start by keeping track of each player's current streak of consecutive wins.
As each game result becomes available, update the winner's streak, and reset the loser's streak to zero.
After each game, check if either player's streak has reached the required number of consecutive wins to win the entire series.
If a player's streak has reached the threshold, that player is the winner and the process stops.
If no player has reached the streak needed to win after all of the games have been played, then there may not be a winner.

Code Implementation

def find_first_winner(results, consecutive_wins):
    player1_wins = 0
    player2_wins = 0

    for result in results:
        if result == 1:
            # Player 1 won, so increment their wins.
            player1_wins += 1
            player2_wins = 0
        else:
            # Player 2 won, so increment their wins.
            player2_wins += 1
            player1_wins = 0

        # Check if player 1 has reached the target wins.
        if player1_wins == consecutive_wins:

            return 1

        # Check if player 2 has reached the target wins.
        if player2_wins == consecutive_wins:

            return 2

    # No player reached the required number of wins in a row.
    return 0

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the game results once, where n is the number of games played. Inside the loop, it updates the consecutive win counts for each player and checks if either player has reached the required number of consecutive wins, which are all constant-time operations. Therefore, the time complexity is directly proportional to the number of games played, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm utilizes a fixed number of integer variables to store the consecutive win counts for each player. These variables are independent of the number of games played (N) or the required number of consecutive wins (K). Therefore, the auxiliary space required remains constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
wins array is null or empty	Return -1 immediately, as no player can win if there are no games.
k is less than or equal to 0	Return -1 immediately, as it's impossible to win a non-positive number of games in a row.
k is greater than n (length of wins array)	Return -1 immediately, as it's impossible to win more games in a row than total games played.
wins array contains values other than 1 or 2	Treat any value other than 1 or 2 as an invalid game and potentially return -1 if the valid game values do not lead to a winner.
wins array contains all 1s or all 2s and k is less than or equal to n	The first player (1 or 2) will win with k games in a row.
No player wins k games in a row	Iterate through the entire wins array and return -1 if no player achieves k consecutive wins.
n is very large (e.g., 10^5) and k is small (e.g., 2)	The sliding window approach avoids recomputing counts for each position, ensuring efficiency even with large n.
n is very large and k is also very large (close to n)	The sliding window approach still works; however, if performance is critical, consider optimizations if there is information about the statistical distribution of wins (e.g., mostly 1s or mostly 2s).