LeetCode 1535 - Find the Winner of an Array Game

LeetCode Problem 1535

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

The problem describes a competitive game played on an array of distinct integers. At every round, only the first two elements are compared. The larger number wins the round and stays at the front of the array, while the smaller number is moved to the end. This process repeats until one number achieves k consecutive wins.

In simpler terms, we repeatedly compare the current champion, which sits at index 0, against the next challenger at index 1. If the champion wins again, its consecutive win streak increases. If the challenger is larger, the challenger becomes the new champion and starts a fresh streak of 1.

The input consists of:

• arr, an array of distinct integers.
• k, the number of consecutive wins required to end the game.

The expected output is the integer that eventually reaches k consecutive wins.

The constraints are important because they strongly influence the type of solution we can afford:

• arr.length can be as large as 10^5, meaning any quadratic simulation would be too slow.
• k can be as large as 10^9, which makes naive round-by-round simulation impossible if we literally simulate until k wins.
• All integers are distinct, which guarantees there are no ties during comparisons.
• The problem guarantees there will always be a winner.

A key observation from the constraints is that k can be much larger than the array size. Since the largest number in the array can never lose once it reaches the front, eventually it must become the winner. This insight helps us avoid simulating billions of rounds.

Some important edge cases to keep in mind include:

• When k is extremely large, much larger than arr.length, because a naive simulation could run far too long.
• When the maximum element is already at the beginning, since it may immediately dominate the game.
• When the winner appears after several champion changes, requiring careful tracking of consecutive victories.
• Very small arrays such as length 2, where the larger element always wins.

Approaches

Brute Force Approach

A straightforward idea is to literally simulate the game exactly as described. We repeatedly compare the first two elements, keep the larger one at the front, move the smaller one to the back, and track consecutive wins.

This approach is correct because it follows the problem statement exactly. Eventually, one element will achieve k consecutive victories and the simulation ends.

However, this method becomes impractical when k is very large. Since k can reach 10^9, we may need to simulate billions of rounds before terminating. Even though the game has repeating structure, the brute-force approach does not exploit it, making it far too slow.

Optimal Approach, Champion Tracking

The key insight is that we do not actually need to simulate the entire queue movement.

Notice what happens during the game:

• The winner of each comparison stays at the front.
• The loser moves away and becomes irrelevant for the current streak.
• Eventually, the largest element in the array must reach the front.
• Once the largest element reaches the front, it can never lose again because all elements are distinct.

This means we can process the array in a single pass while maintaining a current champion and its consecutive win count.

We compare the champion against each new element:

• If the champion is larger, it wins another round.
• If the challenger is larger, the challenger becomes the new champion with a streak of 1.
• As soon as the streak reaches k, we return the champion.

If no element reaches k wins during traversal, then the maximum element must be the answer.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(n)	Simulates the queue exactly, too slow when k is huge
Optimal	O(n)	O(1)	Tracks the current champion without full simulation

Algorithm Walkthrough

1. Initialize the current champion as the first element of the array.

The first element naturally starts as the champion because the game always begins with arr[0] versus arr[1]. 2. Initialize a consecutive win counter to 0.

This variable tracks how many rounds the current champion has won in a row. 3. Iterate through the array starting from index 1.

Each element acts as the next challenger against the current champion. 4. Compare the champion and challenger.

• If the champion is greater, increment the consecutive win counter because the champion wins another round.
• If the challenger is greater, update the champion to the challenger and reset the win counter to 1, since the new champion has just won its first round.

5. After every comparison, check whether the champion has reached k consecutive wins.

If so, immediately return the champion because the game ends at that point. 6. If the loop finishes without anyone reaching k wins, return the champion.

At this stage, the champion must be the largest element in the array, which can never lose.

Why it works

The core invariant is that the variable champion always represents the current front element after processing each comparison. Every round in the actual game compares the current champion against the next challenger, exactly matching our iteration order.

Because all elements are distinct, the maximum element can never lose. Therefore, if no number reaches k wins during traversal, the maximum element must eventually dominate forever. Since our champion will eventually become the maximum element, returning it is correct.

Python Solution

from typing import List

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

        for i in range(1, len(arr)):
            challenger = arr[i]

            if champion > challenger:
                consecutive_wins += 1
            else:
                champion = challenger
                consecutive_wins = 1

            if consecutive_wins >= k:
                return champion

        return champion

The implementation begins by assigning the first element as the current champion and setting consecutive_wins to 0.

We then iterate through the rest of the array, treating each element as a challenger. If the champion is larger, it continues winning and the streak increases. Otherwise, the challenger replaces the champion and starts a new streak of 1.

After each comparison, we check whether the champion has achieved k wins. If it has, we return immediately.

If the loop finishes without reaching k, the champion at that point must be the maximum element in the array, which is guaranteed to eventually win.

Go Solution

func getWinner(arr []int, k int) int {
	champion := arr[0]
	consecutiveWins := 0

	for i := 1; i < len(arr); i++ {
		challenger := arr[i]

		if champion > challenger {
			consecutiveWins++
		} else {
			champion = challenger
			consecutiveWins = 1
		}

		if consecutiveWins >= k {
			return champion
		}
	}

	return champion
}

The Go implementation follows the exact same logic as the Python version. Since the problem guarantees a valid array with at least two elements, we can safely access arr[0] without additional checks.

Go slices are used directly, and integer overflow is not a concern because values stay well within Go's integer range. No extra data structures are needed, so the implementation remains constant in memory usage.

Worked Examples

Example 1

Input:

arr = [2,1,3,5,4,6,7], k = 2

We track the current champion and consecutive wins.

Step	Challenger	Champion Before	Winner	Champion After	Consecutive Wins
Start	-	2	-	2	0
1	1	2	2	2	1
2	3	2	3	3	1
3	5	3	5	5	1
4	4	5	5	5	2

At step 4, the champion 5 reaches 2 consecutive wins, so we return 5.

Output:

5

Example 2

Input:

arr = [3,2,1], k = 10

Step	Challenger	Champion Before	Winner	Champion After	Consecutive Wins
Start	-	3	-	3	0
1	2	3	3	3	1
2	1	3	3	3	2

The loop ends before reaching 10 wins. At this point, 3 is still the champion and is also the maximum element. Since the maximum element can never lose, it would continue winning forever.

Output:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan through the array once
Space	O(1)	Only a few variables are used

The time complexity is O(n) because each array element participates in at most one comparison during the scan. We never repeatedly rotate the array or simulate unnecessary rounds.

The space complexity is O(1) because we only store the current champion and consecutive win count, regardless of input size.

Test Cases

solution = Solution()

# Provided examples
assert solution.getWinner([2, 1, 3, 5, 4, 6, 7], 2) == 5  # example 1
assert solution.getWinner([3, 2, 1], 10) == 3  # example 2

# Smallest valid array
assert solution.getWinner([1, 2], 1) == 2  # larger element wins immediately
assert solution.getWinner([5, 1], 100) == 5  # max element dominates

# k = 1
assert solution.getWinner([2, 8, 3, 1], 1) == 8  # first round winner

# Maximum element already first
assert solution.getWinner([10, 5, 3, 1], 3) == 10  # champion never changes

# Maximum element appears later
assert solution.getWinner([1, 9, 8, 7, 6], 2) == 9  # new champion emerges

# Multiple champion switches
assert solution.getWinner([4, 2, 6, 3, 9], 2) == 9  # several transitions

# Very large k
assert solution.getWinner([1, 25, 35, 42, 68], 10**9) == 68  # largest survives

# Increasing sequence
assert solution.getWinner([1, 2, 3, 4, 5], 2) == 5  # champion keeps changing

# Decreasing sequence
assert solution.getWinner([9, 8, 7, 6], 3) == 9  # first element dominates

Test	Why
[2,1,3,5,4,6,7], k=2	Validates the first provided example
[3,2,1], k=10	Confirms handling of very large k
[1,2], k=1	Smallest valid array
[5,1], k=100	Winner determined despite huge k
k=1 case	Ensures immediate termination works
Maximum already first	Verifies uninterrupted winning streak
Maximum appears later	Tests champion replacement logic
Multiple champion switches	Confirms streak reset behavior
Very large k	Ensures no excessive simulation
Increasing sequence	Tests repeated champion changes
Decreasing sequence	Tests stable initial champion

Edge Cases

One important edge case occurs when k is much larger than the array length, such as k = 10^9. A naive simulation might attempt billions of rounds, leading to time limit exceeded errors. Our implementation avoids this entirely because it only scans the array once. Once the maximum element becomes champion, it is guaranteed to win forever.

Another edge case happens when the largest element already appears at the beginning of the array. In this situation, the first element may immediately accumulate wins without ever being replaced. The implementation handles this naturally because the champion remains unchanged and its streak increases until k is reached.

A third important edge case occurs when multiple champion changes happen early, such as an increasing array like [1,2,3,4,5]. A buggy implementation might fail to reset the consecutive win counter after replacing the champion. Our solution correctly resets the streak to 1 whenever a new champion wins its first match.

Finally, the minimum array size of 2 deserves attention. Since there are only two numbers, the larger one always wins immediately and continues winning forever. The implementation works correctly because the single comparison establishes the proper champion.