3175. Find The First Player to win K Games in a Row

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

1. Initialize two variables: cnt to count the consecutive wins and res to store the index of the current winner.
2. Iterate through the players starting from the second player (index 1).
3. 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, update res to the current player's index and reset cnt to 1 (since this is their first win in the current sequence). - If the current player has a lower skill, increment cnt since the current front player has won another game.
4. Continue this process until either the end of the skills array is reached or the front player wins k consecutive games.
5. Return the index stored in res, which represents the initial index of the player who won k 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.