Watch 6 video solutions for Find The First Player to win K Games in a Row, a medium level problem involving Array, Simulation. This walkthrough by Aryan Mittal has 2,024 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 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:
[0,2,3,4,1].[2,3,4,1,0].[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:
[1,2,0].[1,0,2].[1,2,0].Player 1 won k = 3 games in a row, so the winner is player 1.
Constraints:
n == skills.length2 <= n <= 1051 <= k <= 1091 <= skills[i] <= 106skills are unique.Problem Overview: You are given an array where each value represents a player's skill. Players compete from the front of the line: the first two fight, the stronger player stays at the front, and the loser moves to the end. The first player to achieve k consecutive wins is the answer.
Approach 1: Simulate the Queue (O(n + k) time, O(n) space)
This method directly follows the rules of the game using a queue-style simulation. Compare the first two players, keep the winner at the front, and push the loser to the back of the queue. Maintain a counter tracking how many consecutive wins the current champion has achieved. If the champion wins again, increment the counter; otherwise reset it for the new winner. Continue until a player reaches k wins. This approach models the game exactly and is straightforward to reason about using arrays and simulation techniques, though it may perform many iterations when k is large.
Approach 2: Early Termination Using Maximum Skill (O(n) time, O(1) space)
The key observation: the player with the maximum skill in the array can never lose. Once this player reaches the front, they will keep winning every match afterward. Track the current champion and their consecutive wins while scanning the array from left to right. Each new player challenges the champion; if their skill is higher, they become the new champion and the win counter resets to one. Otherwise the champion wins and the counter increases. As soon as the counter reaches k, return that player's index. If the scan finishes without reaching k, the maximum-skill player will eventually dominate and become the answer. This removes the need for explicit queue rotation and keeps the algorithm linear.
Recommended for interviews: The optimized maximum-skill approach is typically expected. Simulating the queue demonstrates that you understand the mechanics of the problem, but recognizing that the global maximum will eventually win indefinitely shows stronger algorithmic insight and leads to the optimal O(n) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate the Queue | O(n + k) | O(n) | When implementing the game rules directly or verifying the process step‑by‑step. |
| Early Termination Using Maximum Skill | O(n) | O(1) | Best general solution; avoids full simulation and works efficiently for large k. |