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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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 <= 10^5
  • 1 <= k <= 10^9
  • 1 <= skills[i] <= 10^6
  • All integers in skills are unique.

Solution

Method 1 – Simulation with Queue

Intuition

Simulate the process by keeping track of the current winner and their consecutive wins. The winner stays at the front, and the loser moves to the end. The first player to reach k consecutive wins is the answer.

Approach

  1. Initialize a queue with the player indices in order.
  2. Track the current winner and their consecutive win count.
  3. For each round:
    • Compare the first two players in the queue by skill.
    • The winner stays at the front, the loser goes to the end.
    • If the winner is the same as the previous winner, increment their win count; otherwise, reset the count.
    • If the win count reaches k, return the winner’s original index.
  4. If k >= n, the player with the highest skill will eventually win k times in a row.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        int n = skills.size();
        deque<int> q;
        for (int i = 0; i < n; ++i) q.push_back(i);
        int win = 0, cur = q[0];
        while (win < k) {
            int a = q[0], b = q[1];
            if (skills[a] > skills[b]) {
                q.push_back(q[1]);
                q.erase(q.begin() + 1);
                if (cur == a) ++win;
                else { cur = a; win = 1; }
            } else {
                q.push_back(q[0]);
                q.erase(q.begin());
                cur = b; win = 1;
            }
            if (win == k) return cur;
        }
        return cur;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func findWinningPlayer(skills []int, k int) int {
    n := len(skills)
    q := make([]int, n)
    for i := range q { q[i] = i }
    win, cur := 0, q[0]
    for win < k {
        a, b := q[0], q[1]
        if skills[a] > skills[b] {
            q = append(q, q[1])
            q = append(q[:1], q[2:]...)
            if cur == a {
                win++
            } else {
                cur = a
                win = 1
            }
        } else {
            q = append(q, q[0])
            q = q[1:]
            cur = b
            win = 1
        }
        if win == k {
            return cur
        }
    }
    return cur
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        int n = skills.length;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) q.add(i);
        int win = 0, cur = q.peekFirst();
        while (win < k) {
            int a = q.peekFirst(), b = q.toArray(new Integer[0])[1];
            if (skills[a] > skills[b]) {
                q.addLast(b);
                q.remove(b);
                if (cur == a) win++;
                else { cur = a; win = 1; }
            } else {
                q.addLast(a);
                q.removeFirst();
                cur = b; win = 1;
            }
            if (win == k) return cur;
        }
        return cur;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun findWinningPlayer(skills: IntArray, k: Int): Int {
        val n = skills.size
        val q = ArrayDeque<Int>()
        for (i in 0 until n) q.add(i)
        var win = 0
        var cur = q.first()
        while (win < k) {
            val a = q.first()
            val b = q.elementAt(1)
            if (skills[a] > skills[b]) {
                q.addLast(b)
                q.remove(b)
                if (cur == a) win++
                else { cur = a; win = 1 }
            } else {
                q.addLast(a)
                q.removeFirst()
                cur = b; win = 1
            }
            if (win == k) return cur
        }
        return cur
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def findWinningPlayer(self, skills: list[int], k: int) -> int:
        from collections import deque
        n = len(skills)
        q = deque(range(n))
        win = 0
        cur = q[0]
        while win < k:
            a, b = q[0], q[1]
            if skills[a] > skills[b]:
                q.append(q[1])
                q.remove(q[1])
                if cur == a:
                    win += 1
                else:
                    cur = a
                    win = 1
            else:
                q.append(q[0])
                q.popleft()
                cur = b
                win = 1
            if win == k:
                return cur
        return cur
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

use std::collections::VecDeque;
impl Solution {
    pub fn find_winning_player(skills: Vec<i32>, k: i32) -> i32 {
        let n = skills.len();
        let mut q: VecDeque<usize> = (0..n).collect();
        let (mut win, mut cur) = (0, q[0]);
        while win < k {
            let a = q[0];
            let b = q[1];
            if skills[a] > skills[b] {
                q.push_back(q[1]);
                q.remove(1);
                if cur == a {
                    win += 1;
                } else {
                    cur = a;
                    win = 1;
                }
            } else {
                q.push_back(q[0]);
                q.pop_front();
                cur = b;
                win = 1;
            }
            if win == k {
                return cur as i32;
            }
        }
        cur as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    findWinningPlayer(skills: number[], k: number): number {
        const n = skills.length;
        const q: number[] = Array.from({length: n}, (_, i) => i);
        let win = 0, cur = q[0];
        while (win < k) {
            const a = q[0], b = q[1];
            if (skills[a] > skills[b]) {
                q.push(q[1]);
                q.splice(1, 1);
                if (cur === a) win++;
                else { cur = a; win = 1; }
            } else {
                q.push(q[0]);
                q.shift();
                cur = b; win = 1;
            }
            if (win === k) return cur;
        }
        return cur;
    }
}

Complexity

  • ⏰ Time complexity: O(n + k), as each round processes at most one player to the end, and the winner is found in at most n + k steps.
  • 🧺 Space complexity: O(n), for the queue.