Find The First Player to win K Games in a Row

Find The First Player to win K Games in a Row - Problem

Array Simulation Medium

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.

Input & Output

Example 1 — Basic Competition

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

› Output: 4

💡 Note: Player 4 has the highest skill (9). After several games, player 4 reaches the front and wins 3 consecutive games, so return index 4.

Example 2 — Early Winner

$ Input: skills = [2,1,3], k = 1

› Output: 0

💡 Note: Since k=1, we only need one win. Player 0 (skill=2) beats player 1 (skill=1) in the first game, so return index 0.

Example 3 — Small k Value

$ Input: skills = [1,9,8,2,3], k = 2

› Output: 1

💡 Note: Player 1 (skill=9) beats player 0, then beats player 2. Two consecutive wins with k=2, so return index 1.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of player skills and target consecutive wins k

Process

Players compete pairwise, winner stays front, loser goes back

Output

Index of first player to achieve k consecutive wins

Key Takeaway

🎯 Key Insight: The strongest player will eventually dominate once they reach the front of the queue

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is that once the player with maximum skill reaches the front of the queue, they will win all subsequent games. The optimal approach simulates the competition while tracking consecutive wins, with an early exit optimization when the strongest player takes the lead. Time: O(n + k), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Simulation	O(n * k)	O(n)	Simulate each game by maintaining the queue and tracking consecutive wins
Optimized Simulation	O(n + k)	O(n)	Recognize that the strongest player will eventually win once they reach the front

Direct Simulation — Algorithm Steps

Initialize queue with all players in order
Simulate each game: compare first two players
Track consecutive wins for current leader
Return when someone reaches k wins

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Queue

Players lined up by index: [0,1,2,3,4]

Game Simulation

First two players compete, winner stays front, loser goes back

Track Wins

Count consecutive wins until k is reached

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* skills, int skillsSize, int k) {
    if (k == 1) {
        return skills[0] > skills[1] ? 0 : 1;
    }
    
    int* queue = (int*)malloc(skillsSize * sizeof(int));
    for (int i = 0; i < skillsSize; i++) {
        queue[i] = i;
    }
    
    int front = 0, rear = skillsSize;
    int wins = 0;
    
    while (1) {
        int player1 = queue[front++];
        int player2 = queue[front++];
        
        int winner, loser;
        if (skills[player1] > skills[player2]) {
            winner = player1;
            loser = player2;
        } else {
            winner = player2;
            loser = player1;
        }
        
        // Move elements to make room at front
        for (int i = rear; i > front; i--) {
            queue[i] = queue[i-1];
        }
        queue[front] = winner;
        queue[rear++] = loser;
        
        if (winner == queue[front]) {
            wins++;
        } else {
            wins = 1;
        }
        
        if (wins == k) {
            free(queue);
            return winner;
        }
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int skills[1000];
    int skillsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            skills[skillsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(skills, skillsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * k)

In worst case, need k wins and each win processes through n players

✓ Linear Growth

Space Complexity

O(n)

Queue to store all n players

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler