Find the Winner of an Array Game: Simulation with Early Exit

LeetCode Find the Winner of an Array Game (problem 1535) gives you an integer array arr of distinct integers and an integer k. A game plays out between the first two elements of the array each round. The larger element wins and stays at position 0, while the loser moves to the end of the array. The game ends when one element wins k consecutive rounds. Return that element.

At first glance, this looks like it requires actually rotating the array repeatedly. But there is a much cleaner approach that solves it in a single pass with O(1) space.

Why this problem matters

Simulation problems show up frequently in interviews, and they often come with a trap: the naive simulation works but is far too slow for large inputs. The real test is whether you can spot the shortcut. In this case, the shortcut is recognizing that you never need to physically move elements around. You just need to walk through the array once, tracking who is currently winning.

This pattern of "simulate the idea, not the mechanics" appears in many array problems. Once you see it here, you will recognize it elsewhere.

The key insight

You do not need to rotate the array at all. Think about what happens during the game. The current champion at position 0 fights each challenger in sequence. If the champion beats a challenger, the win counter increments. If a challenger wins, it becomes the new champion and the counter resets to 1.

Here is the critical observation: once the maximum element in the array reaches position 0, it will never lose. It will beat every subsequent challenger. So if k is large enough (specifically, if k >= n - 1), the answer is simply the maximum element.

Even for smaller k, you can simulate the process in a single left-to-right pass. You never need to wrap around. Why? Because if no element achieves k consecutive wins before you reach the end of the array, the current champion at that point must be the maximum element, and it will win every future round.

The solution

def get_winner(arr: list[int], k: int) -> int:
    current = arr[0]
    wins = 0
    for i in range(1, len(arr)):
        if arr[i] > current:
            current = arr[i]
            wins = 1
        else:
            wins += 1
        if wins == k:
            return current
    return current

The variable current tracks the reigning champion, and wins counts how many consecutive challengers it has beaten. You iterate through the array starting at index 1. Each element is a new challenger.

If the challenger is larger, it becomes the new champion with 1 win (it just beat the previous champion). If the champion is larger, its win count goes up by 1. The moment wins reaches k, you return the champion immediately.

If you finish the loop without anyone reaching k wins, the current champion has beaten every other element. It is the maximum, and it will win forever, so you return it.

Visual walkthrough

Let's trace through arr = [2, 1, 3, 5, 4, 6, 7] with k = 2. We need to find the first element that wins 2 consecutive rounds.

In this example with k = 2, the element 5 wins two consecutive rounds (beating 3 and then 4), so the answer is 5. Notice how we never needed to physically rearrange the array. We just walked through it, tracking the current champion and counting wins.

Complexity analysis

Time: O(n). You visit each element at most once. The loop runs through arr[1:], and you either update the champion or increment the win counter at each step. The early exit when wins == k can only make this faster.

Space: O(1). You use two variables (current and wins) regardless of input size. No extra data structures needed.

A naive simulation that actually rotates the array would cost O(n * k) in the worst case, since each rotation is O(n) and you might need up to k rounds. For large k, that could be extremely slow. The single-pass approach avoids this entirely.

The building blocks

1. Running champion pattern

The core technique here is maintaining a "running champion" as you scan through an array. You keep track of the best element seen so far and compare each new element against it. This same pattern shows up when finding the maximum element, the longest streak, or any "king of the hill" scenario.

champion = arr[0]
for i in range(1, len(arr)):
    if arr[i] > champion:
        champion = arr[i]

The difference in this problem is that you also track how many consecutive elements the champion has beaten, adding a counter on top of the basic pattern.

2. Early exit optimization

The early return when wins == k is a form of short-circuit evaluation. You do not need to process the entire array if you already have your answer. This optimization is especially powerful when k is small relative to n.

The final return current after the loop handles the opposite case: when k is very large. If no element achieves k wins during the pass, the survivor is the global maximum, and it wins everything from that point on.

Edge cases

k = 1. The first comparison determines the winner. It is simply max(arr[0], arr[1]).

k >= n - 1. The answer is always max(arr). Once the maximum element reaches position 0, it beats every remaining element, accumulating n - 1 consecutive wins. Any k value at or above n - 1 will be satisfied by the maximum.

Array of length 2. Only one comparison ever happens. The larger of the two elements wins immediately, regardless of k.

Maximum element is at index 0. It wins every round from the start. The answer is arr[0] as long as k is at most n - 1 (which it always is, since the maximum beats everyone).

From understanding to recall

This problem is a good example of why pattern recognition matters more than memorization. The solution is short, but arriving at it requires seeing past the surface-level simulation. You need to realize that the "game" is really just a linear scan in disguise.

The two building blocks here, running champion and early exit, are simple on their own. But combining them under interview pressure, especially when the problem is dressed up as a game simulation, requires having drilled these patterns until they are automatic. That is what spaced repetition gives you: the ability to see through the costume and recognize the underlying structure.

Related posts

• Majority Element - Another problem about tracking a "winner" through an array
• Gas Station - Single-pass simulation with early exit optimization
• Jump Game - Greedy single-pass array problem

The real lesson from this problem is that many simulation problems do not actually require simulation. When you see a problem that says "repeat this process until X happens," ask yourself: can I predict the outcome without running every step? Often the answer is yes, and the solution collapses from a complex loop into a clean single pass.