Find The First Player to win K Games in a Row

Med

#2820Time: O(N^2). The number of games simulated is at most `O(N)`. Each game involves list modifications that take `O(N)` time.Space: O(N) to store the player indices in the `ArrayList`.1 company

Data structures

Array

Companies

IBM

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the game process described in the problem statement using an ArrayList to represent the queue of players. While it's a straightforward translation of the rules, its performance is hampered by the choice of data structure. Operations like removing from the front of an ArrayList are costly, making this solution impractical for the given constraints.

Algorithm

Create an ArrayList to store the queue of player indices, from 0 to n-1.
Initialize a currentWinnerIdx and winStreak variable to track the winning player and their streak.
Enter a loop that continues as long as no player has won k games.
Inside the loop, get the first two players from the list, p1 and p2.
Compare their skills to find the winner and loser.
Update the winStreak. If the winner is the same as currentWinnerIdx, increment the streak. Otherwise, update currentWinnerIdx and reset the streak to 1.
If winStreak equals k, return currentWinnerIdx.
Modify the list to reflect the game's outcome: remove the two players from the front and add the winner to the front and the loser to the back. This step is inefficient with an ArrayList.

Walkthrough

In this method, we initialize an ArrayList with player indices from 0 to n-1. We then enter a simulation loop. In each iteration, we identify the first two players in the list, compare their skills, and determine the winner and loser. We update the list by removing the two contestants and re-inserting them according to the rules: the winner at the front, the loser at the back. We also maintain a count of consecutive wins for the current champion. The simulation stops and returns the champion's index as soon as their win streak reaches k. The main drawback is that list.remove(0) and list.add(0, element) are O(N) operations, and since the simulation can run up to O(N) games, the total time complexity becomes quadratic.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int findWinningPlayer(int[] skills, int k) {6        int n = skills.length;7        List<Integer> queue = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            queue.add(i);10        }11 12        // Optimization for very large k to pass some cases13        if (k >= n) {14            int maxIdx = 0;15            for (int i = 1; i < n; i++) {16                if (skills[i] > skills[maxIdx]) {17                    maxIdx = i;18                }19            }20            return maxIdx;21        }22 23        int currentWinnerIdx = -1;24        int winStreak = 0;25 26        while (true) {27            int p1_idx = queue.get(0);28            int p2_idx = queue.get(1);29 30            int winnerIdx, loserIdx;31            if (skills[p1_idx] > skills[p2_idx]) {32                winnerIdx = p1_idx;33                loserIdx = p2_idx;34            } else {35                winnerIdx = p2_idx;36                loserIdx = p1_idx;37            }38 39            if (winnerIdx == currentWinnerIdx) {40                winStreak++;41            } else {42                currentWinnerIdx = winnerIdx;43                winStreak = 1;44            }45 46            if (winStreak == k) {47                return currentWinnerIdx;48            }49 50            // Inefficient queue update using ArrayList51            queue.remove(0);52            queue.remove(0);53            queue.add(0, winnerIdx);54            queue.add(loserIdx);55        }56    }57}

Complexity

Time

O(N^2). The number of games simulated is at most `O(N)`. Each game involves list modifications that take `O(N)` time.

Space

O(N) to store the player indices in the `ArrayList`.

Trade-offs

Pros

Conceptually simple and easy to map from the problem description.

Cons

Extremely inefficient due to the use of an ArrayList for queue operations.
Removing elements from the front of an ArrayList takes O(N) time, leading to a poor overall time complexity.
Will likely result in a 'Time Limit Exceeded' error on platforms with larger test cases.

This approach significantly improves upon the previous one by choosing a more suitable data structure. By using a Deque (like ArrayDeque in Java), all queue operations—getting players from the front, adding the winner to the front, and adding the loser to the back—can be performed in constant time. The simulation logic remains the same, but the efficiency is greatly enhanced.

Algorithm

Use a Deque (Double-Ended Queue), such as ArrayDeque, which is optimized for adding and removing elements from both ends.
Populate the Deque with player indices from 0 to n-1.
Keep track of the winnerIdx and their winStreak.
Loop until a player's winStreak reaches k.
In each iteration, use pollFirst() to get the two players at the front of the queue.
Compare their skills to determine the winner and loser.
Use addFirst(winner) to place the winner at the front and addLast(loser) to place the loser at the back. These are O(1) operations.
Update the winStreak and winnerIdx accordingly.
Return winnerIdx when winStreak equals k.

Walkthrough

The core idea is still to simulate the tournament game by game. However, we replace the ArrayList with a Deque. This is crucial because a Deque provides O(1) time complexity for adding or removing elements from either the head or the tail.

The simulation proceeds as follows: we take the first two players, they compete, the winner is put back at the front, and the loser at the end. We track the current winner and their streak. The key insight for the time complexity is that the total number of games that need to be simulated is bounded by O(N). This is because after a certain number of games (at most 2N-2), the player with the highest skill will have reached the front and defeated every other player, establishing a permanent winning streak. Therefore, the simulation will always terminate in a linear number of steps.

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public int findWinningPlayer(int[] skills, int k) {6        int n = skills.length;7        Deque<Integer> queue = new ArrayDeque<>();8        for (int i = 0; i < n; i++) {9            queue.add(i);10        }11 12        if (k >= n) {13            int maxIdx = 0;14            for (int i = 1; i < n; i++) {15                if (skills[i] > skills[maxIdx]) {16                    maxIdx = i;17                }18            }19            return maxIdx;20        }21 22        int winnerIdx = queue.peekFirst();23        int winStreak = 0;24 25        while (winStreak < k) {26            int p1 = queue.pollFirst();27            int p2 = queue.pollFirst();28            29            if (skills[p1] > skills[p2]) {30                queue.addFirst(p1);31                queue.addLast(p2);32                if (winnerIdx == p1) {33                    winStreak++;34                } else {35                    winnerIdx = p1;36                    winStreak = 1;37                }38            } else {39                queue.addFirst(p2);40                queue.addLast(p1);41                winnerIdx = p2;42                winStreak = 1;43            }44        }45        return winnerIdx;46    }47}

Complexity

Time

O(N). The number of games is bounded by `O(N)`, and each game is processed in `O(1)` time.

Space

O(N) to store the `Deque` of player indices.

Trade-offs

Pros

Efficient O(N) time complexity.
Correctly models the game dynamics.
Handles all constraints effectively.

Cons

Requires extra space proportional to the number of players.

This is the most optimal solution, achieving linear time complexity with constant extra space. It avoids creating an explicit queue data structure. Instead, it recognizes that the game is a series of challenges where a reigning winner defends their position against subsequent players in the initial lineup. We only need to track the current winner's index and their win streak as we iterate through the challengers once.

Algorithm

Initialize current_winner_idx = 0 and consecutive_wins = 0.
Iterate through the players from index i = 1 to n-1, treating each as a challenger.
In each iteration, compare the skill of the current_winner_idx with the challenger i.
If the current winner wins (skills[current_winner_idx] > skills[i]): Increment consecutive_wins.
If the challenger wins (skills[i] > skills[current_winner_idx]): Update current_winner_idx to i and reset consecutive_wins to 1.
After each game, check if consecutive_wins == k. If it is, return current_winner_idx.
If the loop finishes, it means the current_winner_idx holds the index of the strongest player overall. This player will never lose again, so they are the guaranteed winner. Return current_winner_idx.

Walkthrough

We can simulate the process without an actual queue. The player at the front of the queue is the current winner. They will play against every subsequent player until they are defeated. If they are defeated, the challenger becomes the new winner, and the simulation continues from there.

We can implement this with a single pass. We start by assuming player 0 is the winner. We then iterate from player 1 to n-1. In each step, we pit the current_winner against the challenger i. If the winner prevails, their win streak increases. If the challenger wins, they become the new winner, and their streak starts at 1. If at any point a player's streak reaches k, they are the answer.

A crucial observation is what happens if the loop completes without anyone reaching k wins. The player who is the current_winner at the end of the loop must have a higher skill than all players who came after them. This means they are the player with the highest skill in the entire array. They will never be defeated again and will eventually reach k wins. Thus, they are the final answer.

1class Solution {2    public int findWinningPlayer(int[] skills, int k) {3        int n = skills.length;4        int current_winner_idx = 0;5        int consecutive_wins = 0;6 7        for (int i = 1; i < n; i++) {8            if (skills[current_winner_idx] > skills[i]) {9                consecutive_wins++;10            } else {11                current_winner_idx = i;12                consecutive_wins = 1;13            }14 15            if (consecutive_wins == k) {16                return current_winner_idx;17            }18        }19 20        // If the loop completes, the current winner is the strongest player overall.21        // They will keep winning, so they are the answer for any remaining k.22        return current_winner_idx;23    }24}

Complexity

Time

O(N), as we perform a single pass through the skills array.

Space

O(1), as we only use a few variables to store the state.

Trade-offs

Pros

Optimal O(N) time complexity.
Optimal O(1) space complexity.
Elegant and concise implementation.

Cons

The logic might be slightly less direct to derive compared to a literal queue simulation.

Solutions

Solution

1class Solution {2public3  int findWinningPlayer(int[] skills, int k) {4    int n = skills.length;5    k = Math.min(k, n - 1);6    int i = 0, cnt = 0;7    for (int j = 1; j < n; ++j) {8      if (skills[i] < skills[j]) {9        i = j;10        cnt = 1;11      } else {12        ++cnt;13      }14      if (cnt == k) {15        break;16      }17    }18    return i;19  }20}

1class Solution {2public:3  int findWinningPlayer(vector<int> &skills, int k) {4    int n = skills.size();5    k = min(k, n - 1);6    int i = 0, cnt = 0;7    for (int j = 1; j < n; ++j) {8      if (skills[i] < skills[j]) {9        i = j;10        cnt = 1;11      } else {12        ++cnt;13      }14      if (cnt == k) {15        break;16      }17    }18    return i;19  }20};

1class Solution:2    def findWinningPlayer(self, skills: List[int], k: int) -> int: n = len(skills) k = min(k, n - 1) i = cnt = 0 for j in range(1, n): if skills[i] < skills[j]: i = j cnt = 1 else: cnt += 1 if cnt == k: break return i

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int findWinningPlayer(int[] skills, int k) {4    int n = skills.length;5    k = Math.min(k, n - 1);6    int i = 0, cnt = 0;7    for (int j = 1; j < n; ++j) {8      if (skills[i] < skills[j]) {9        i = j;10        cnt = 1;11      } else {12        ++cnt;13      }14      if (cnt == k) {15        break;16      }17    }18    return i;19  }20}

1class Solution {2public:3  int findWinningPlayer(vector<int> &skills, int k) {4    int n = skills.size();5    k = min(k, n - 1);6    int i = 0, cnt = 0;7    for (int j = 1; j < n; ++j) {8      if (skills[i] < skills[j]) {9        i = j;10        cnt = 1;11      } else {12        ++cnt;13      }14      if (cnt == k) {15        break;16      }17    }18    return i;19  }20};

1class Solution:2    def findWinningPlayer(self, skills: List[int], k: int) -> int: n = len(skills) k = min(k, n - 1) i = cnt = 0 for j in range(1, n): if skills[i] < skills[j]: i = j cnt = 1 else: cnt += 1 if cnt == k: break return i

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.