
Intuition
The problem involves a series of games where players compete in a queue, and the winner of each game stays at the front while the loser moves to the back. The goal is to determine the initial index of the first player who wins k
consecutive games. The intuition is to simulate this process efficiently, keeping track of consecutive wins for the current front player until the required condition is met.
Approach
- Initialize two variables:
cnt
to count the consecutive wins andres
to store the index of the current winner. - Iterate through the players starting from the second player (index 1).
- In each iteration, compare the skill of the current player with the skill of the player at the front of the queue (
skills[res]
): - If the current player has a higher skill, updateres
to the current player's index and resetcnt
to 1 (since this is their first win in the current sequence). - If the current player has a lower skill, incrementcnt
since the current front player has won another game. - Continue this process until either the end of the
skills
array is reached or the front player winsk
consecutive games. - Return the index stored in
res
, which represents the initial index of the player who wonk
consecutive games.
Complexity
- Time complexity: O(n) - The algorithm processes each player exactly once, resulting in a linear time complexity.
- Space complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size.
Code
C++
class Solution {
public:
int findWinningPlayer(vector& skills, int k) {
int cnt = 0; // Counter for consecutive wins
int res = 0; // Index of the current winner
// Iterate over the players starting from the second one
for (int i = 1; cnt < k && i < skills.size(); ++i) {
if (skills[res] < skills[i]) {
// If current player has a higher skill, update the current winner
res = i;
cnt = 1; // Reset the consecutive win counter
} else {
// If current winner wins again, increment the counter
++cnt;
}
}
return res; // Return the index of the player who won k consecutive games
}
};
Python
class Solution:
def findWinningPlayer(self, skills: List[int], k: int) -> int:
cnt = 0 # Counter for consecutive wins
res = 0 # Index of the current winner
# Iterate over the players starting from the second one
for i in range(1, len(skills)):
if cnt >= k:
break
if skills[res] < skills[i]:
# If current player has a higher skill, update the current winner
res = i
cnt = 1 # Reset the consecutive win counter
else:
# If current winner wins again, increment the counter
cnt += 1
return res # Return the index of the player who won k consecutive games
Java
class Solution {
public int findWinningPlayer(int[] skills, int k) {
int cnt = 0; // Counter for consecutive wins
int res = 0; // Index of the current winner
// Iterate over the players starting from the second one
for (int i = 1; cnt < k && i < skills.length; ++i) {
if (skills[res] < skills[i]) {
// If current player has a higher skill, update the current winner
res = i;
cnt = 1; // Reset the consecutive win counter
} else {
// If current winner wins again, increment the counter
++cnt;
}
}
return res; // Return the index of the player who won k consecutive games
}
}
JavaScript
/**
* @param {number[]} skills
* @param {number} k
* @return {number}
*/
var findWinningPlayer = function (skills, k) {
var cnt = 0; // Counter for consecutive wins
var res = 0; // Index of the current winner
// Iterate over the players starting from the second one
for (var i = 1; cnt < k && i < skills.length; ++i) {
if (skills[res] < skills[i]) {
// If current player has a higher skill, update the current winner
res = i;
cnt = 1; // Reset the consecutive win counter
} else {
// If current winner wins again, increment the counter
++cnt;
}
}
return res; // Return the index of the player who won k consecutive games
};
Go
func findWinningPlayer(skills []int, k int) int {
cnt := 0 // Counter for consecutive wins
res := 0 // Index of the current winner
// Iterate over the players starting from the second one
for i := 1; cnt < k && i < len(skills); i++ {
if skills[res] < skills[i] {
// If current player has a higher skill, update the current winner
res = i
cnt = 1 // Reset the consecutive win counter
} else {
// If current winner wins again, increment the counter
cnt++
}
}
return res // Return the index of the player who won k consecutive games
}
C#
public class Solution {
public int FindWinningPlayer(int[] skills, int k) {
int cnt = 0; // Counter for consecutive wins
int res = 0; // Index of the current winner
// Iterate over the players starting from the second one
for (int i = 1; cnt < k && i < skills.Length; ++i) {
if (skills[res] < skills[i]) {
// If current player has a higher skill, update the current winner
res = i;
cnt = 1; // Reset the consecutive win counter
} else {
// If current winner wins again, increment the counter
++cnt;
}
}
return res; // Return the index of the player who won k consecutive games
}
}
Conclusion
The FindWinningPlayer
method in the Solution
class efficiently determines the initial index of the first player to win k
consecutive games in a queue-based competition. The method iterates through the player skills, keeping track of consecutive wins and updating the current winner as necessary. It terminates early when the winner wins k
consecutive games. The solution runs in O(n) time complexity, where n is the number of players, and O(1) space complexity. This makes it an optimal solution for the problem.