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

### [Problem link](https://leetcode.com/problems/find-the-first-player-to-win-k-games-in-a-row/)

###### tags: `leedcode` `medium` `c++` `Greedy`

A competition consists of <code>n</code> players numbered from <code>0</code> to <code>n - 1</code>.

You are given an integer array <code>skills</code> of size <code>n</code> and a **positive** integer <code>k</code>, where <code>skills[i]</code> is the skill level of player <code>i</code>. All integers in <code>skills</code> are **unique** .

All players are standing in a queue in order from player <code>0</code> to player <code>n - 1</code>.

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 <code>k</code> games **in a row** .

Return the initial index of the winning player.

**Example 1:**

<div class="example-block">
Input: <span class="example-io">skills = [4,2,6,3,9], k = 2

Output: 2

Explanation:

Initially, the queue of players is <code>[0,1,2,3,4]</code>. 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 <code>[0,2,3,4,1]</code>.
- 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 <code>[2,3,4,1,0]</code>.
- 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 <code>[2,4,1,0,3]</code>.

Player 2 won <code>k = 2</code> 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 <code>[0,1,2]</code>. 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 <code>[1,2,0]</code>.
- 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 <code>[1,0,2]</code>.
- 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 <code>[1,2,0]</code>.

Player 1 won <code>k = 3</code> games in a row, so the winner is player 1.

**Constraints:**

- <code>n == skills.length</code>
- <code>2 <= n <= 10⁵</code>
- <code>1 <= k <= 10⁹</code>
- <code>1 <= skills[i] <= 10⁶</code>
- All integers in <code>skills</code> are unique.

## Solution 1 - Greedy
#### C++

class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        int maxIdx = 0;
        int strike = -1;
        for (int i = 0; i < skills.size(); i++) {
            if (skills[i] > skills[maxIdx]) {
                maxIdx = i;
                strike = 0;
            }
            strike++;
            if (strike == k) {
                break;
            }
        }
        return maxIdx;
    }
};

>### Complexity
>n = skills.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
x