We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find The First Player to win K Games in a Row

Difficulty: Medium

Problem Description

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.

Key Insights

  • Players compete in pairs based on their order in the queue.
  • The winner remains at the front of the queue, while the loser moves to the back.
  • The competition continues until one player wins k consecutive games.
  • The skill levels are unique, allowing for a straightforward comparison of players' abilities.

Space and Time Complexity

Time Complexity: O(n + k)
Space Complexity: O(n)

Solution

We can simulate the competition using a queue data structure to manage the players' order. We will iterate through the games by comparing the skill levels of the first two players in the queue. The winner is determined based on their skill levels, and we keep track of the number of consecutive wins for the current winner. If a player wins k games in a row, we return their initial index. We can use a deque for efficient popping and appending operations.

Code Solutions

from collections import deque

def find_winner(skills, k):
    n = len(skills)
    # Create a queue with player indices
    queue = deque(range(n))
    # Track wins for the current winner
    current_winner = queue[0]
    consecutive_wins = 0
    
    while True:
        # Get the first two players
        player1 = queue.popleft()
        player2 = queue.popleft()
        
        if skills[player1] > skills[player2]:
            # Player 1 wins
            winner = player1
            loser = player2
        else:
            # Player 2 wins
            winner = player2
            loser = player1
            
        # Increment the wins for the current winner
        if winner == current_winner:
            consecutive_wins += 1
        else:
            current_winner = winner
            consecutive_wins = 1  # Reset for new winner
            
        # Check for the winning condition
        if consecutive_wins == k:
            return current_winner
        
        # Winner stays and loser goes to the end
        queue.append(winner)
        queue.append(loser)
← Back to All Questions