# Find The First Player to win K Games in a Row
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-first-player-to-win-k-games-in-a-row)
Canonical: https://scaleengineer.com/dsa/problems/find-the-first-player-to-win-k-games-in-a-row
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## 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.length`
* `2 <= n <= 105`
* `1 <= k <= 109`
* `1 <= skills[i] <= 106`
* All integers in `skills` are unique.

# Approaches
## Simulation using an ArrayList
This approach directly simulates the game process described in the problem statement using an `ArrayList` to represent the queue of players. While it's a straightforward translation of the rules, its performance is hampered by the choice of data structure. Operations like removing from the front of an `ArrayList` are costly, making this solution impractical for the given constraints.
**Time:** O(N^2). The number of games simulated is at most `O(N)`. Each game involves list modifications that take `O(N)` time. · **Space:** O(N) to store the player indices in the `ArrayList`.
**Pros:** Conceptually simple and easy to map from the problem description.
**Cons:** Extremely inefficient due to the use of an `ArrayList` for queue operations.; Removing elements from the front of an `ArrayList` takes `O(N)` time, leading to a poor overall time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms with larger test cases.
### Explanation
In this method, we initialize an `ArrayList` with player indices from `0` to `n-1`. We then enter a simulation loop. In each iteration, we identify the first two players in the list, compare their skills, and determine the winner and loser. We update the list by removing the two contestants and re-inserting them according to the rules: the winner at the front, the loser at the back. We also maintain a count of consecutive wins for the current champion. The simulation stops and returns the champion's index as soon as their win streak reaches `k`. The main drawback is that `list.remove(0)` and `list.add(0, element)` are `O(N)` operations, and since the simulation can run up to `O(N)` games, the total time complexity becomes quadratic.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        int n = skills.length;
        List<Integer> queue = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            queue.add(i);
        }

        // Optimization for very large k to pass some cases
        if (k >= n) {
            int maxIdx = 0;
            for (int i = 1; i < n; i++) {
                if (skills[i] > skills[maxIdx]) {
                    maxIdx = i;
                }
            }
            return maxIdx;
        }

        int currentWinnerIdx = -1;
        int winStreak = 0;

        while (true) {
            int p1_idx = queue.get(0);
            int p2_idx = queue.get(1);

            int winnerIdx, loserIdx;
            if (skills[p1_idx] > skills[p2_idx]) {
                winnerIdx = p1_idx;
                loserIdx = p2_idx;
            } else {
                winnerIdx = p2_idx;
                loserIdx = p1_idx;
            }

            if (winnerIdx == currentWinnerIdx) {
                winStreak++;
            } else {
                currentWinnerIdx = winnerIdx;
                winStreak = 1;
            }

            if (winStreak == k) {
                return currentWinnerIdx;
            }

            // Inefficient queue update using ArrayList
            queue.remove(0);
            queue.remove(0);
            queue.add(0, winnerIdx);
            queue.add(loserIdx);
        }
    }
}
```
### Algorithm
- Create an `ArrayList` to store the queue of player indices, from `0` to `n-1`.
- Initialize a `currentWinnerIdx` and `winStreak` variable to track the winning player and their streak.
- Enter a loop that continues as long as no player has won `k` games.
- Inside the loop, get the first two players from the list, `p1` and `p2`.
- Compare their skills to find the `winner` and `loser`.
- Update the `winStreak`. If the `winner` is the same as `currentWinnerIdx`, increment the streak. Otherwise, update `currentWinnerIdx` and reset the streak to 1.
- If `winStreak` equals `k`, return `currentWinnerIdx`.
- Modify the list to reflect the game's outcome: remove the two players from the front and add the `winner` to the front and the `loser` to the back. This step is inefficient with an `ArrayList`.

## Efficient Simulation with a Deque
This approach significantly improves upon the previous one by choosing a more suitable data structure. By using a `Deque` (like `ArrayDeque` in Java), all queue operations—getting players from the front, adding the winner to the front, and adding the loser to the back—can be performed in constant time. The simulation logic remains the same, but the efficiency is greatly enhanced.
**Time:** O(N). The number of games is bounded by `O(N)`, and each game is processed in `O(1)` time. · **Space:** O(N) to store the `Deque` of player indices.
**Pros:** Efficient `O(N)` time complexity.; Correctly models the game dynamics.; Handles all constraints effectively.
**Cons:** Requires extra space proportional to the number of players.
### Explanation
The core idea is still to simulate the tournament game by game. However, we replace the `ArrayList` with a `Deque`. This is crucial because a `Deque` provides `O(1)` time complexity for adding or removing elements from either the head or the tail.

The simulation proceeds as follows: we take the first two players, they compete, the winner is put back at the front, and the loser at the end. We track the current winner and their streak. The key insight for the time complexity is that the total number of games that need to be simulated is bounded by `O(N)`. This is because after a certain number of games (at most `2N-2`), the player with the highest skill will have reached the front and defeated every other player, establishing a permanent winning streak. Therefore, the simulation will always terminate in a linear number of steps.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        int n = skills.length;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.add(i);
        }

        if (k >= n) {
            int maxIdx = 0;
            for (int i = 1; i < n; i++) {
                if (skills[i] > skills[maxIdx]) {
                    maxIdx = i;
                }
            }
            return maxIdx;
        }

        int winnerIdx = queue.peekFirst();
        int winStreak = 0;

        while (winStreak < k) {
            int p1 = queue.pollFirst();
            int p2 = queue.pollFirst();
            
            if (skills[p1] > skills[p2]) {
                queue.addFirst(p1);
                queue.addLast(p2);
                if (winnerIdx == p1) {
                    winStreak++;
                } else {
                    winnerIdx = p1;
                    winStreak = 1;
                }
            } else {
                queue.addFirst(p2);
                queue.addLast(p1);
                winnerIdx = p2;
                winStreak = 1;
            }
        }
        return winnerIdx;
    }
}
```
### Algorithm
- Use a `Deque` (Double-Ended Queue), such as `ArrayDeque`, which is optimized for adding and removing elements from both ends.
- Populate the `Deque` with player indices from `0` to `n-1`.
- Keep track of the `winnerIdx` and their `winStreak`.
- Loop until a player's `winStreak` reaches `k`.
- In each iteration, use `pollFirst()` to get the two players at the front of the queue.
- Compare their skills to determine the `winner` and `loser`.
- Use `addFirst(winner)` to place the winner at the front and `addLast(loser)` to place the loser at the back. These are `O(1)` operations.
- Update the `winStreak` and `winnerIdx` accordingly.
- Return `winnerIdx` when `winStreak` equals `k`.

## Single-Pass Simulation with Constant Space
This is the most optimal solution, achieving linear time complexity with constant extra space. It avoids creating an explicit queue data structure. Instead, it recognizes that the game is a series of challenges where a reigning winner defends their position against subsequent players in the initial lineup. We only need to track the current winner's index and their win streak as we iterate through the challengers once.
**Time:** O(N), as we perform a single pass through the skills array. · **Space:** O(1), as we only use a few variables to store the state.
**Pros:** Optimal `O(N)` time complexity.; Optimal `O(1)` space complexity.; Elegant and concise implementation.
**Cons:** The logic might be slightly less direct to derive compared to a literal queue simulation.
### Explanation
We can simulate the process without an actual queue. The player at the front of the queue is the current winner. They will play against every subsequent player until they are defeated. If they are defeated, the challenger becomes the new winner, and the simulation continues from there.

We can implement this with a single pass. We start by assuming player `0` is the winner. We then iterate from player `1` to `n-1`. In each step, we pit the `current_winner` against the challenger `i`. If the winner prevails, their win streak increases. If the challenger wins, they become the new winner, and their streak starts at 1. If at any point a player's streak reaches `k`, they are the answer.

A crucial observation is what happens if the loop completes without anyone reaching `k` wins. The player who is the `current_winner` at the end of the loop must have a higher skill than all players who came after them. This means they are the player with the highest skill in the entire array. They will never be defeated again and will eventually reach `k` wins. Thus, they are the final answer.

```java
class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        int n = skills.length;
        int current_winner_idx = 0;
        int consecutive_wins = 0;

        for (int i = 1; i < n; i++) {
            if (skills[current_winner_idx] > skills[i]) {
                consecutive_wins++;
            } else {
                current_winner_idx = i;
                consecutive_wins = 1;
            }

            if (consecutive_wins == k) {
                return current_winner_idx;
            }
        }

        // If the loop completes, the current winner is the strongest player overall.
        // They will keep winning, so they are the answer for any remaining k.
        return current_winner_idx;
    }
}
```
### Algorithm
- Initialize `current_winner_idx = 0` and `consecutive_wins = 0`.
- Iterate through the players from index `i = 1` to `n-1`, treating each as a challenger.
- In each iteration, compare the skill of the `current_winner_idx` with the challenger `i`.
- If the current winner wins (`skills[current_winner_idx] > skills[i]`): Increment `consecutive_wins`.
- If the challenger wins (`skills[i] > skills[current_winner_idx]`): Update `current_winner_idx` to `i` and reset `consecutive_wins` to `1`.
- After each game, check if `consecutive_wins == k`. If it is, return `current_winner_idx`.
- If the loop finishes, it means the `current_winner_idx` holds the index of the strongest player overall. This player will never lose again, so they are the guaranteed winner. Return `current_winner_idx`.

# Solutions
### Java

```java
class Solution {
public
  int findWinningPlayer(int[] skills, int k) {
    int n = skills.length;
    k = Math.min(k, n - 1);
    int i = 0, cnt = 0;
    for (int j = 1; j < n; ++j) {
      if (skills[i] < skills[j]) {
        i = j;
        cnt = 1;
      } else {
        ++cnt;
      }
      if (cnt == k) {
        break;
      }
    }
    return i;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findWinningPlayer(vector<int> &skills, int k) {
    int n = skills.size();
    k = min(k, n - 1);
    int i = 0, cnt = 0;
    for (int j = 1; j < n; ++j) {
      if (skills[i] < skills[j]) {
        i = j;
        cnt = 1;
      } else {
        ++cnt;
      }
      if (cnt == k) {
        break;
      }
    }
    return i;
  }
};

```

### Python

```python
class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int: n = len(skills) k = min(k, n - 1) i = cnt = 0 for j in range(1, n): if skills[i] < skills[j]: i = j cnt = 1 else: cnt += 1 if cnt == k: break return i

```