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

MediumArraySimulation

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The approach to solving this problem is based on the observation of how the queue shifts over the course of the competition:

Each game is determined by comparing the first two players in the queue.
After each game, the winner stays, and the loser goes to the end of the queue. Therefore, the players' relative positions in terms of skills influence the sequence of games.
If a player wins consecutively k times, that player becomes the winner.

The solution operates by iterating over the players while maintaining some key observations:

We set a maximum win streak count cnt to keep track of how many consecutive games a player has won. If a player’s skill wins a competition against the current leader, they take that position and reset cnt.
The iteration continues until a player wins k consecutive games, and that player's initial position is returned as the result.
Special consideration is given when k is larger than or equal to n-1. In such cases, the player with the highest skill level will ultimately emerge as the winner. This is why we use k = min(k, n - 1).

This understanding provides an efficient method to determine the initial index of the winning player using only a single pass through the list, achieving an O(n) time complexity.

Solution Approach

The solution makes use of a simple yet effective algorithm to determine the winner of the competition by closely following the rules of the game. Here's how the implementation works:

Initialization:
- Determine the number of players, n, from the length of the skills array.
- Set k to the minimum of k and n-1. This is because if k is larger, we only need a maximum consecutive win streak of n-1 to determine the winner.
Tracking Wins:
- Initialize a variable i to track the index of the current leading player and set a counter cnt to measure the consecutive wins.
- Iterate over the array starting from the second player (index 1).
Comparison and Update:
- For each player j in the iteration starting from the second position:
  - Compare the skill level of the current leading player skills[i] with the skill level of the current player skills[j].
  - If the skill of the current player j is greater, update i to j (indicating the new potential winner) and reset cnt to 1.
  - If the current leading player i continues to win, increment cnt.
- If cnt reaches k, break the loop as we have found the winner.
Return Statement:
- Return the index i, the position of the player who wins k games in a row.

This algorithm relies on the fact that a player who can continually maintain leadership without defeat for k consecutive games will eventually be the winner. The approach efficiently uses a single pass (O(n)) with constant space (O(1)), making it optimal for the problem.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have skills = [3, 1, 5, 2, 4] and k = 2.

Step 1: Initialization

Number of players, n = 5.
Adjust k to min(k, n-1) = min(2, 4) = 2.
Initialize i = 0 (current leader index) and cnt = 0 (consecutive win count).

Step 2: Iterating Through Players

Begin iterating from the second player, i.e., j = 1.

Iteration Details:

Compare players 0 and 1:
- skills[0] = 3 vs. skills[1] = 1
- Player 0 wins; increment cnt to 1.
Compare players 0 and 2:
- skills[0] = 3 vs. skills[2] = 5
- Player 2 has a higher skill; update leader to i = 2, reset cnt to 1.
Compare players 2 and 3:
- skills[2] = 5 vs. skills[3] = 2
- Player 2 wins again; increment cnt to 2.

At this point, cnt = 2, which matches k. The loop terminates because Player 2 has won k consecutive games.

Step 3: Return Statement

Return i = 2. The player at initial index 2, which corresponds to the skill level 5, wins the competition.

This walkthrough shows how the queue processing and iterative comparison lead to identifying the winner efficiently. The initial index of the winning player is 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findWinningPlayer(self, skills: List[int], k: int) -> int:
5        # Length of the skills list
6        n = len(skills)
7      
8        # Limit k to be at most n-1 to avoid unnecessary comparisons
9        k = min(k, n - 1)
10      
11        # 'i' is the index of the current winning player
12        # 'cnt' counts consecutive wins of the current player
13        i = cnt = 0
14      
15        # Iterate over players starting from the second player
16        for j in range(1, n):
17            # If the current winning player is weaker than player 'j'
18            if skills[i] < skills[j]:
19                # Player 'j' becomes the new winning player
20                i = j
21                cnt = 1  # Reset the counter for consecutive wins
22            else:
23                # Increment win count of the current winning player
24                cnt += 1
25              
26            # If the current player has won 'k' consecutive times
27            if cnt == k:
28                break
29      
30        # Return the index of the player who won 'k' consecutive times
31        return i
32

1class Solution {
2    public int findWinningPlayer(int[] skills, int k) {
3        int n = skills.length; // Determine the number of players
4
5        // Ensure k is not greater than n-1, as there are only n-1 possible wins
6        k = Math.min(k, n - 1);
7
8        int currentIndex = 0; // Start with the first player
9        int consecutiveWins = 0; // Counter for consecutive wins
10
11        // Iterate through each player starting from the second one
12        for (int j = 1; j < n; ++j) {
13            if (skills[currentIndex] < skills[j]) {
14                // Player at index j has more skills than current winner
15                currentIndex = j; // Update the current winner's index
16                consecutiveWins = 1; // Reset the win count to 1
17            } else {
18                // Current winner wins again
19                ++consecutiveWins; // Increment the consecutive win counter
20            }
21
22            // Break the loop if the current player wins 'k' consecutive rounds
23            if (consecutiveWins == k) {
24                break;
25            }
26        }
27        return currentIndex; // Return the index of the winning player
28    }
29}
30

1class Solution {
2public:
3    int findWinningPlayer(std::vector<int>& skills, int k) {
4        int n = skills.size(); // Get the number of players
5        k = std::min(k, n - 1); // Ensure k doesn't exceed the maximum possible victories
6        int currentIndex = 0; // Index of the currently leading player
7        int consecutiveWins = 0; // Count of consecutive victories by the current leader
8
9        // Iterate over each player starting from the second player
10        for (int nextPlayer = 1; nextPlayer < n; ++nextPlayer) {
11            // If the next player has more skill, update the current leader
12            if (skills[currentIndex] < skills[nextPlayer]) {
13                currentIndex = nextPlayer; // Update the current leader
14                consecutiveWins = 1; // Reset consecutive wins for the new leader
15            } else {
16                ++consecutiveWins; // Increment consecutive wins
17            }
18
19            // If the current leader has won k times consecutively, stop the comparison
20            if (consecutiveWins == k) {
21                break;
22            }
23        }
24        return currentIndex; // Return the index of the winning player
25    }
26};
27

1// Function to find the winning player based on the skills array and the number of consecutive wins needed.
2function findWinningPlayer(skills: number[], k: number): number {
3    const n = skills.length; // Total number of players
4
5    // Limit k to be no greater than n - 1, as a player needs at least one other player to win against.
6    k = Math.min(k, n - 1);
7
8    let i = 0; // Index of the current winner
9    let cnt = 0; // Count of consecutive wins
10
11    // Iterate over each player starting from the second player
12    for (let j = 1; j < n; ++j) {
13        // If the current player at index j has more skills than the current winner
14        if (skills[i] < skills[j]) {
15            i = j; // Update the winner to the current player
16            cnt = 1; // Reset the win count
17        } else {
18            ++cnt; // Increment win count for the current winner
19        }
20
21        // If the current winner has won consecutively k times, break the loop
22        if (cnt === k) {
23            break;
24        }
25    }
26
27    // Return the index of the winning player
28    return i;
29}
30

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the skills list. This is because the algorithm processes each player in the list once, making a single pass through the list.

The space complexity of the code is O(1), as it only uses a fixed amount of additional space regardless of the size of the input list skills. The variables i, cnt, n, and k do not depend on the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: