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

The problem describes a competition where players stand in a queue and repeatedly compete against each other. Every player has a unique skill value, and whenever two players play, the one with the larger skill always wins. At each step: 1.

leetcodemediumarraysimulation

LeetCode Problem 3175

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

The problem describes a competition where players stand in a queue and repeatedly compete against each other. Every player has a unique skill value, and whenever two players play, the one with the larger skill always wins.

At each step:

  1. The first two players in the queue compete.
  2. The stronger player stays at the front.
  3. The weaker player moves to the back of the queue.

The competition ends as soon as one player achieves k consecutive wins. We must return the original index of that player.

The input array skills represents the skill level of each player. The player’s index in the array is also their identifier. For example, if skills[2] = 6, then player 2 has skill 6.

The constraints are very important:

  • n can be as large as 10^5
  • k can be as large as 10^9

These limits immediately tell us that we cannot literally simulate every game when k is huge. A direct queue simulation could potentially take billions of operations, which would be far too slow.

The problem also guarantees that all skill values are unique. This matters because every game always has a single clear winner, there are no ties to handle.

An important observation is that the strongest player in the entire array can never lose once they reach the front of the queue. Eventually, that player will win forever. This property is the key to the optimal solution.

Several edge cases are worth noticing early:

  • If k = 1, the winner is simply whoever wins the very first game.
  • If k is larger than n, the global maximum skill player must eventually win.
  • If the strongest player starts near the front, the answer may appear very quickly.
  • If the strongest player starts near the end, several leadership changes may happen before the final winner emerges.

Approaches

Brute Force Approach

A straightforward solution is to literally simulate the queue exactly as described.

We can use a deque:

  • Pop the first two players.
  • Compare their skill values.
  • Put the winner back at the front.
  • Push the loser to the back.
  • Track consecutive wins for the current champion.

This approach is correct because it directly follows the rules of the competition.

However, the problem is efficiency. The number of games could become extremely large when k is large. Since k can reach 10^9, simulating every match is infeasible.

The brute force solution may take up to O(k) operations, which is far too slow.

Key Insight for the Optimal Solution

We do not actually need to maintain the entire queue.

The current front player behaves similarly to a running champion:

  • Compare the current champion against the next player.
  • The stronger player becomes the new champion.
  • Track how many consecutive wins the current champion has.

The critical observation is this:

Once the player with the maximum skill becomes champion, they can never lose again.

That means the process stabilizes very quickly. Since there are only n players, the strongest player must appear after at most n - 1 comparisons.

Therefore:

  • We only need a single pass through the array.
  • We keep track of the current champion and their consecutive wins.
  • As soon as the consecutive wins reach k, we return the champion.

If nobody reaches k during the scan, then the strongest player is guaranteed to eventually win, so we return them.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k) O(n) Simulates the actual queue process
Optimal O(n) O(1) Tracks only the current champion and streak

Algorithm Walkthrough

  1. Start with player 0 as the current champion.

The first player is initially at the front of the queue, so they are the first active champion. 2. Initialize the consecutive win counter to 0.

This counter tracks how many games the current champion has won in a row. 3. Iterate through the remaining players from left to right.

Each new player represents the next challenger in the queue. 4. Compare the current champion’s skill with the challenger’s skill.

  • If the champion’s skill is larger, the champion wins again.
  • Increment the consecutive win counter.
  • The champion remains unchanged.
  1. If the challenger’s skill is larger:
  • The challenger becomes the new champion.
  • Reset the consecutive win counter to 1, because this new champion has just won one game.
  1. After every match, check whether the current champion has reached k consecutive wins.
  • If yes, immediately return that champion’s original index.
  1. If the loop finishes without anyone reaching k wins:
  • The current champion must be the player with the maximum skill.
  • Since they can never lose again, they will eventually accumulate enough wins.
  • Return their index.

Why it works

The algorithm maintains an invariant:

  • The current champion is always the strongest player among all players seen so far.

Whenever a stronger challenger appears, they replace the champion. Otherwise, the champion continues winning.

Because skills are unique, the globally strongest player eventually becomes champion and never loses afterward. Therefore, if no earlier player achieves k consecutive wins, the maximum skill player must eventually do so.

Python Solution

from typing import List

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        n = len(skills)

        champion = 0
        consecutive_wins = 0

        for challenger in range(1, n):
            if skills[champion] > skills[challenger]:
                consecutive_wins += 1
            else:
                champion = challenger
                consecutive_wins = 1

            if consecutive_wins >= k:
                return champion

        return champion

The implementation follows the exact logic from the algorithm walkthrough.

The variable champion stores the index of the current front player. Instead of physically rotating a queue, we only track who currently dominates the competition.

The loop processes each challenger exactly once. For every comparison:

  • If the champion is stronger, they extend their winning streak.
  • Otherwise, the challenger replaces the champion and starts a new streak of length 1.

The moment the streak reaches k, the function immediately returns the champion index.

If the loop completes without returning, then the current champion is the strongest player overall. Since that player cannot lose any future match, they are guaranteed to eventually win k consecutive games.

Go Solution

func findWinningPlayer(skills []int, k int) int {
	n := len(skills)

	champion := 0
	consecutiveWins := 0

	for challenger := 1; challenger < n; challenger++ {
		if skills[champion] > skills[challenger] {
			consecutiveWins++
		} else {
			champion = challenger
			consecutiveWins = 1
		}

		if consecutiveWins >= k {
			return champion
		}
	}

	return champion
}

The Go implementation mirrors the Python logic closely.

Go slices are used directly for the skills array, and integer indices are tracked using standard int variables.

No additional data structures are required, so the implementation remains constant space. Integer overflow is not a concern because all values easily fit inside Go’s standard integer range.

Worked Examples

Example 1

Input:

skills = [4,2,6,3,9]
k = 2

Initial state:

  • Champion = player 0
  • Champion skill = 4
  • Consecutive wins = 0
Challenger Challenger Skill Winner New Champion Consecutive Wins
1 2 Player 0 0 1
2 6 Player 2 2 1
3 3 Player 2 2 2

At this point, player 2 has reached 2 consecutive wins.

Answer:

2

Example 2

Input:

skills = [2,5,4]
k = 3

Initial state:

  • Champion = player 0
  • Champion skill = 2
  • Consecutive wins = 0
Challenger Challenger Skill Winner New Champion Consecutive Wins
1 5 Player 1 1 1
2 4 Player 1 1 2

The loop ends before reaching k = 3.

However, player 1 has the maximum skill value 5, so they can never lose another match. They will eventually achieve 3 consecutive wins.

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each player is processed at most once
Space O(1) Only a few variables are used

The algorithm performs a single linear scan through the array. Every comparison either keeps the current champion or replaces them with a stronger challenger.

No extra data structures proportional to the input size are allocated, so the space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        champion = 0
        consecutive_wins = 0

        for challenger in range(1, len(skills)):
            if skills[champion] > skills[challenger]:
                consecutive_wins += 1
            else:
                champion = challenger
                consecutive_wins = 1

            if consecutive_wins >= k:
                return champion

        return champion

sol = Solution()

assert sol.findWinningPlayer([4,2,6,3,9], 2) == 2  # provided example 1
assert sol.findWinningPlayer([2,5,4], 3) == 1  # provided example 2

assert sol.findWinningPlayer([5,1], 1) == 0  # smallest possible n
assert sol.findWinningPlayer([1,5], 1) == 1  # challenger wins immediately

assert sol.findWinningPlayer([3,2,1], 2) == 0  # first player already strongest
assert sol.findWinningPlayer([1,2,3], 2) == 2  # strongest player at end

assert sol.findWinningPlayer([1,9,3,4,5], 10) == 1  # k much larger than n
assert sol.findWinningPlayer([7,6,5,4,3], 4) == 0  # champion never changes

assert sol.findWinningPlayer([2,1,3,5,4,6,7], 2) == 3  # multiple champion changes
assert sol.findWinningPlayer([10,1,2,3,4], 3) == 0  # initial player dominates

print("All test cases passed!")

Test Case Summary

Test Why
[4,2,6,3,9], k=2 Validates the first official example
[2,5,4], k=3 Validates the second official example
[5,1], k=1 Smallest valid input size
[1,5], k=1 Immediate challenger victory
[3,2,1], k=2 Initial player already strongest
[1,2,3], k=2 Strongest player appears late
[1,9,3,4,5], k=10 Very large k relative to n
[7,6,5,4,3], k=4 Champion never changes
[2,1,3,5,4,6,7], k=2 Multiple champion transitions
[10,1,2,3,4], k=3 First player wins repeatedly

Edge Cases

One important edge case occurs when k = 1. In this scenario, the competition ends after the very first game. A buggy implementation might accidentally continue processing additional players. The current solution handles this naturally because the first comparison immediately produces a streak of length 1, triggering the return condition.

Another important case is when k is much larger than the number of players. A naive queue simulation could run for billions of rounds before stopping. The optimized solution avoids this entirely. Once the maximum skill player becomes champion, the algorithm simply returns them after the scan completes, because they are guaranteed to eventually accumulate enough consecutive wins.

A third tricky case happens when the strongest player appears near the end of the array. Several leadership changes can happen before the final dominant player emerges. The implementation correctly handles this because the champion variable is continuously updated whenever a stronger challenger appears.

A fourth subtle case is when the first player is already the strongest player overall. In that situation, the champion never changes throughout the entire process. The implementation efficiently increments the consecutive win counter without performing any unnecessary queue operations.