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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find The First Player to win K Games in a Row

Number: 3413

Difficulty: Medium

Paid? No

Companies: IBM

Problem Description

A competition involves n players, each with a unique skill level given in the skills array. Initially, the players are lined up in order. In each game, the first two players in the queue compete, and the player with the higher skill wins the game. The winner remains at the front with an incremented win streak while the loser is moved to the end of the queue. This process continues until a player wins k consecutive games. The task is to return the original index of the player who first reaches k consecutive wins.

Key Insights

  • The simulation uses a queue to represent the order of players.
  • In each round, compare the first two players; the higher skilled player wins.
  • Maintain a counter for consecutive wins for the current leader.
  • Once a player reaches k consecutive wins, they are declared the winner.
  • Optimization: If k is large enough (k >= n - 1), the player with the maximum skill will eventually win, so directly return their index.

Space and Time Complexity

Time Complexity: O(n) in the optimal case with early termination when the max-skill player is reached; otherwise, O(n + k) in simulation. Space Complexity: O(n) due to the usage of a queue for simulation.

Solution

We simulate the competition using a queue (or similar data structure). At each step:

  1. Dequeue the first two players.
  2. Compare their skill levels.
  3. The winner (with the higher skill) remains (and has their win counter incremented), and the loser is enqueued at the back.
  4. If the win counter reaches k, the simulation stops and returns the winner’s original index.
  5. An early exit is applied if k is very large: the player with the maximum skill (who never loses once reached) will eventually win, so their index is returned immediately.

Code Solutions

Below are sample implementations in various languages:

from collections import deque

def findWinner(skills, k):
    n = len(skills)
    max_skill = max(skills)
    # Early return if k >= n-1 since max skill will eventually win all rounds.
    if k >= n - 1:
        return skills.index(max_skill)
    
    dq = deque(skills)
    current = dq.popleft()
    win_streak = 0

    while win_streak < k:
        challenger = dq.popleft()
        if current > challenger:
            win_streak += 1
            dq.append(challenger)
        else:
            dq.append(current)
            current = challenger
            win_streak = 1
    return skills.index(current)

# Example usage:
if __name__ == "__main__":
    skills = [4,2,6,3,9]
    k = 2
    print(findWinner(skills, k))
← Back to All Questions