Find The First Player to win K Games in a Row solution and explanation
IBM
5 more videos on this problem
3175. Find The First Player to win K Games in a Row | 2 Approaches | One Pass | SimulationAryan Mittal · 16:24 · 2K views
100297 Find The First Player to win K Games in a Row | leetcode || contest 132 || solved | javaSsquare · 0:58 · 176 views
3175. Find The First Player to win K Games in a Row (Leetcode Medium)Programming Live with Larry · 8:07 · 134 views
3175. Find The First Player to win K Games in a Row | GreedyTech Courses · 7:28 · 111 views
LeetCode 3175 | Find The First Player to win K Games in a Row | Biweekly Contest 132 | Arrays | DSAAlgo Horizon · 12:25 · 91 views
Live Coding:Step-by-Step LeetCode Problem Solving-3175 Find the First Player to Win K Games in a RowLeetcode onii-chan · 17:28 · 27 views
The problem
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.
def find_first_winner(skills, k):
win_count = 0
current_winner_index = 0
for i in range(1, len(skills)):
if skills[current_winner_index] > skills[i]:
win_count += 1
else:
current_winner_index = i
win_count = 1
if win_count == k:
return current_winner_index
return current_winner_index # The strongest skill wins by default.
skills = [4, 2, 6, 3, 9]
k = 2
winner = find_first_winner(skills, k)
print(f"Winner: {winner}")public class Main {
public static int findFirstWinner(int[] skills, int k) {
int winCount = 0;
int currentWinnerIndex = 0;
for (int i = 1; i < skills.length; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex; // The strongest skill wins by default.
}
public static void main(String[] args) {
int[] skills = {4, 2, 6, 3, 9};
int k = 2;
int winner = findFirstWinner(skills, k);
System.out.println("Winner: " + winner);
}
}#include <vector>
int findFirstWinner(const std::vector<int>& skills, int k) {
int winCount = 0;
int currentWinnerIndex = 0;
for (size_t i = 1; i < skills.size(); ++i) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex; // The strongest skill wins by default.
}
int main() {
std::vector<int> skills = {4, 2, 6, 3, 9};
int k = 2;
int winner = findFirstWinner(skills, k);
std::cout << "Winner: " << winner << std::endl;
return 0;
}function findFirstWinner(skills, k) {
let winCount = 0;
let currentWinnerIndex = 0;
for (let i = 1; i < skills.length; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount === k) return currentWinnerIndex;
}
return currentWinnerIndex; // The strongest skill wins by default.
}
const skills = [4, 2, 6, 3, 9];
const k = 2;
const winner = findFirstWinner(skills, k);
console.log(`Winner: ${winner}`);#include <stdio.h>
int findFirstWinner(int skills[], int n, int k) {
int winCount = 0;
int currentWinnerIndex = 0;
for (int i = 1; i < n; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex; // The strongest skill wins by default.
}
int main() {
int skills[] = {4, 2, 6, 3, 9};
int n = 5;
int k = 2;
int winner = findFirstWinner(skills, n, k);
printf("Winner: %d\n", winner);
return 0;
}using System;
public class Program {
public static int FindFirstWinner(int[] skills, int k) {
int winCount = 0;
int currentWinnerIndex = 0;
for (int i = 1; i < skills.Length; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex; // The strongest skill wins by default.
}
public static void Main() {
int[] skills = {4, 2, 6, 3, 9};
int k = 2;
int winner = FindFirstWinner(skills, k);
Console.WriteLine($"Winner: {winner}");
}
}The Python implementation employs a simple loop to simulate the competition. It adjusts the winning index count whenever a player wins or loses against another one. The process is efficient due to its single pass requirement.
Time Complexity: O(n), traversing through each element once.
Space Complexity: O(1), utilizing constant space independent of input size.
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.
def find_first_winner_with_max_skill(skills, k):
max_skill_index = max(range(len(skills)), key=lambda i: skills[i])
if k > len(skills):
return max_skill_index
win_count = 0
current_winner_index = 0
for i in range(1, len(skills)):
if skills[current_winner_index] > skills[i]:
win_count += 1
else:
current_winner_index = i
win_count = 1
if win_count == k:
return current_winner_index
return current_winner_index
skills = [4, 2, 6, 3, 9]
k = 2
winner = find_first_winner_with_max_skill(skills, k)
print(f"Winner: {winner}")public class Main {
public static int findFirstWinnerWithMaxSkill(int[] skills, int k) {
int maxSkillIndex = 0;
for (int i = 1; i < skills.length; i++) {
if (skills[i] > skills[maxSkillIndex]) {
maxSkillIndex = i;
}
}
if (k > skills.length) return maxSkillIndex;
int winCount = 0;
int currentWinnerIndex = 0;
for (int i = 1; i < skills.length; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex;
}
public static void main(String[] args) {
int[] skills = {4, 2, 6, 3, 9};
int k = 2;
int winner = findFirstWinnerWithMaxSkill(skills, k);
System.out.println("Winner: " + winner);
}
}#include <vector>
int findFirstWinnerWithMaxSkill(const std::vector<int>& skills, int k) {
int maxSkillIndex = 0;
for (size_t i = 1; i < skills.size(); ++i) {
if (skills[i] > skills[maxSkillIndex]) {
maxSkillIndex = i;
}
}
if (k > skills.size()) return maxSkillIndex;
int winCount = 0;
int currentWinnerIndex = 0;
for (size_t i = 1; i < skills.size(); ++i) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex;
}
int main() {
std::vector<int> skills = {4, 2, 6, 3, 9};
int k = 2;
int winner = findFirstWinnerWithMaxSkill(skills, k);
std::cout << "Winner: " << winner << std::endl;
return 0;
}function findFirstWinnerWithMaxSkill(skills, k) {
const maxSkillValue = Math.max(...skills);
const maxSkillIndex = skills.indexOf(maxSkillValue);
if (k > skills.length) return maxSkillIndex;
let winCount = 0;
let currentWinnerIndex = 0;
for (let i = 1; i < skills.length; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount === k) return currentWinnerIndex;
}
return currentWinnerIndex;
}
const skills = [4, 2, 6, 3, 9];
const k = 2;
const winner = findFirstWinnerWithMaxSkill(skills, k);
console.log(`Winner: ${winner}`);#include <stdio.h>
int findFirstWinnerWithMaxSkill(int skills[], int n, int k) {
int maxSkillIndex = 0;
for (int i = 1; i < n; i++) {
if (skills[i] > skills[maxSkillIndex]) {
maxSkillIndex = i;
}
}
if (k > n) return maxSkillIndex;
int winCount = 0;
int currentWinnerIndex = 0;
for (int i = 1; i < n; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex;
}
int main() {
int skills[] = {4, 2, 6, 3, 9};
int n = 5;
int k = 2;
int winner = findFirstWinnerWithMaxSkill(skills, n, k);
printf("Winner: %d\n", winner);
return 0;
}using System;
using System.Linq;
public class Program {
public static int FindFirstWinnerWithMaxSkill(int[] skills, int k) {
int maxSkillIndex = skills.ToList().IndexOf(skills.Max());
if (k > skills.Length) return maxSkillIndex;
int winCount = 0;
int currentWinnerIndex = 0;
for (int i = 1; i < skills.Length; i++) {
if (skills[currentWinnerIndex] > skills[i]) {
winCount++;
} else {
currentWinnerIndex = i;
winCount = 1;
}
if (winCount == k) return currentWinnerIndex;
}
return currentWinnerIndex;
}
public static void Main() {
int[] skills = {4, 2, 6, 3, 9};
int k = 2;
int winner = FindFirstWinnerWithMaxSkill(skills, k);
Console.WriteLine($"Winner: {winner}");
}
}In Python, this solution calculates the index of the maximum skilled player for possibly shortcutting the simulation. If it's needed, regular simulation logic follows similar to the first approach.
Time Complexity: O(n), processes finding max and simulation.
Space Complexity: O(1), employing no extra space beyond fixed variables.
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:
function findWinningPlayer(skills: number[], k: number): number {
const n = skills.length;
k = Math.min(k, n - 1);
let [i, cnt] = [0, 0];
for (let j = 1; j < n; ++j) {
if (skills[i] < skills[j]) {
i = j;
cnt = 1;
} else {
++cnt;
}
if (cnt === k) {
break;
}
}
return i;
}func findWinningPlayer(skills []int, k int) int {
n := len(skills)
k = min(k, n-1)
i, cnt := 0, 0
for j := 1; j < n; j++ {
if skills[i] < skills[j] {
i = j
cnt = 1
} else {
cnt++
}
if cnt == k {
break
}
}
return i
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate the Queue | Time Complexity: O(n), traversing through each element once. |
| Early Termination Using Maximum Skill | Time Complexity: O(n), processes finding max and simulation. |
| Quick Thinking | – |
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. |
Frequently asked questions
Is Find The First Player to win K Games in a Row easy or hard?
This problem is generally classified as Medium difficulty. The simulation idea is simple, but identifying that the maximum skill player will eventually dominate and using that insight to achieve an O(n) solution requires careful reasoning.
Find The First Player to win K Games in a Row Python/Java solution
Python and Java implementations typically follow the linear champion-tracking approach. Maintain variables for the current winner index and consecutive wins, iterate through the array, and update the champion when a stronger player appears. The algorithm remains O(n) time and O(1) space in both languages.
How to solve Find The First Player to win K Games in a Row in O(n)?
Iterate through the skills array while keeping the current champion and their consecutive win count. If the next player's skill is higher, they become the new champion and the counter resets to one. Otherwise the champion's win count increases. Return the champion once the counter reaches k, or return the maximum-skill player if the scan finishes first.
What is the best approach for Find The First Player to win K Games in a Row?
The optimal approach tracks the current champion while scanning the array and uses the observation that the maximum skill player cannot lose. Maintain a consecutive win counter for the champion and update it after each comparison. Once the counter reaches k, return that player's index. This solution runs in O(n) time and O(1) space.
Is Find The First Player to win K Games in a Row asked at Google/Amazon/Meta?
Problems based on queue simulation and competitive comparisons appear frequently in interviews at large tech companies such as Amazon, Google, and Meta. The key skill tested is recognizing patterns in repeated comparisons and optimizing a simulation into a linear scan.
What data structure is used in Find The First Player to win K Games in a Row?
The straightforward approach uses a queue-like structure to simulate players rotating after each match. The optimized solution relies only on array traversal and variables to track the current champion and consecutive wins, eliminating the need for an explicit queue.
What is the time complexity of Find The First Player to win K Games in a Row?
The optimized solution runs in O(n) time because each player is compared at most once while scanning the array. Space complexity is O(1) since only a few variables track the current champion and win count. A direct queue simulation may take O(n + k) time and O(n) space.