Find The First Player to win K Games in a Row - Solution & Explanation
Problem Statement
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.length2 <= n <= 1051 <= k <= 1091 <= skills[i] <= 106- All integers in
skillsare unique.
Approach Overview
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 1: Simulate the Queue
This approach simulates the competition process step by step, managing the players' order using a queue-like mechanism. At each step, the first two players in the queue compete, with the winner staying ahead and the loser moving to the queue's end. We keep a count of consecutive wins for the current player at the front of the queue. The simulation stops when a player reaches k consecutive wins or when the most skillful player can potentially win k games in a row due to player order.
The solution iterates over the list of players after initializing the current winner to the first player. It checks each subsequent player to determine if they are more skilled than the current winner. If so, the current winner changes, resetting the win count. If not, the win count increases. This process continues until the win count reaches k, or until the simulation completes.
Complexity
Time Complexity: O(n), as each player is evaluated once in a single pass through the list.
Space Complexity: O(1), as only a few variables are utilized for indexing and counting.
Approach 2: Early Termination Using Maximum Skill
Since the skills are unique and we know the maximum possible skill in the array, an optimization can be made. If k is extremely large and insurmountable by any other than the highest skilled player, we immediately return this as the winner. This avoids unnecessary simulation when it's evident that a player can win eventually regardless of the match queue due to their superior skill.
This solution first identifies the index of the maximum skill player. If k is greater than the number of players, this player becomes the automatic winner because they can continue to win until it reaches k. Otherwise, the regular simulation proceeds.
Complexity
Time Complexity: O(n), requires two passes for finding max skill and simulating.
Space Complexity: O(1), constant space usage.
Approach 3: Quick Thinking
We notice that each time the first two elements of the array are compared, regardless of the result, the next comparison will always be between the next element in the array and the current winner. Therefore, if we have looped n-1 times, the final winner must be the maximum element in the array. Otherwise, if an element has won consecutively k times, then this element is the final winner.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simulate the Queue | Time Complexity: O(n), as each player is evaluated once in a single pass through the list. |
| Early Termination Using Maximum Skill | Time Complexity: O(n), requires two passes for finding max skill and simulating. |
| Quick Thinking | — |
Detailed Complexity Analysis
| 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. |
Video Solution
3175. Find The First Player to win K Games in a Row | 2 Approaches | One Pass | Simulation • Aryan Mittal • 2,056 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Find The First Player to win K Games in a Row easy or hard?
Find The First Player to win K Games in a Row Python/Java solution
How to solve Find The First Player to win K Games in a Row in O(n)?
What is the best approach for Find The First Player to win K Games in a Row?
Is Find The First Player to win K Games in a Row asked at Google/Amazon/Meta?
What data structure is used in Find The First Player to win K Games in a Row?
What is the time complexity of Find The First Player to win K Games in a Row?
Ready to solve this problem?
Practice Find The First Player to win K Games in a Row with our built-in code editor and test cases.
Practice on FleetCode