#1535

Medium

LeetCode Problem Workspace

Find the Winner of an Array Game

Determine the integer that wins an array game by achieving k consecutive victories through simulated pairwise comparisons.

array simulation

Problem Statement

Given a distinct integer array arr and an integer k, play a game comparing the first two elements repeatedly. In each round, the larger of arr[0] and arr[1] remains at the front, while the smaller moves to the array's end. The game continues until an element wins k rounds consecutively.

Return the integer that wins the game. If k is greater than or equal to the array length, the winner is guaranteed to be the largest element, as it will eventually win k consecutive rounds regardless of initial order.

Examples

Example 1

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

Output: 5

Let's see the rounds of the game: Round | arr | winner | win_count 1 | [2,1,3,5,4,6,7] | 2 | 1 2 | [2,3,5,4,6,7,1] | 3 | 1 3 | [3,5,4,6,7,1,2] | 5 | 1 4 | [5,4,6,7,1,2,3] | 5 | 2 So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2

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

Output: 3

3 will win the first 10 rounds consecutively.

Constraints

2 <= arr.length <= 105
1 <= arr[i] <= 106
arr contains distinct integers.
1 <= k <= 109

Solution Approach

Simulate the Game Iteratively

Maintain a counter for consecutive wins and compare the first two elements of the array in each round. Move the smaller element to the end and increment the winner's count. Reset the count if the first element loses. Continue until the counter reaches k.

Handle Large k Efficiently

If k is equal to or larger than the array length, immediately return the maximum element. This avoids unnecessary simulation since the largest element will inevitably win k consecutive rounds.

Optimize for Space and Time

Use constant space by updating the array in-place and track only the current winner and consecutive wins. This maintains O(n) time complexity and O(1) space, avoiding extra data structures.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each element can be compared at most once before the maximum element secures k wins. Space complexity is O(1) since the array is updated in-place and only counters are maintained.

What Interviewers Usually Probe

Will you simulate each round or find a shortcut based on k?
How do you handle extremely large k values without full simulation?
Can you optimize the solution to constant space without extra data structures?

Common Pitfalls or Variants

Common pitfalls

Failing to reset the consecutive win count when the leading element loses.
Not handling cases where k exceeds array length, leading to unnecessary iterations.
Using extra space unnecessarily instead of tracking only the current winner and count.

Follow-up variants

Find the first element to reach m consecutive wins in a modified array game.
Determine the winner when the comparison rule is based on modulo values instead of direct magnitude.
Extend the game to allow multiple elements to compete in each round and track the first to reach k wins.

FAQ

What is the winner in 'Find the Winner of an Array Game' if k is very large?

If k is equal to or exceeds the array length, the winner is the maximum element, as it will inevitably win k consecutive rounds.

Can I simulate the game using extra arrays or queues?

Yes, but it's unnecessary. Tracking only the current winner and consecutive wins achieves O(1) space, which is more efficient.

How does the array plus simulation pattern apply here?

The problem directly uses pairwise comparisons in an array to simulate the game's progress, embodying the array plus simulation pattern.

What if multiple elements tie in consecutive wins?

The rules guarantee distinct integers, so ties cannot occur in consecutive win counts, simplifying simulation logic.

Is there a shortcut instead of full simulation for small arrays?

Yes, for small arrays or when k >= arr.length, returning the maximum element immediately avoids full iteration.

terminal

Solution

Solution 1: Quick Thinking

We notice that each time the first two elements of the array are compared, regardless of the result, the next comparison will always be between the next element in the array and the current winner. Therefore, if we have looped $n-1$ times, the final winner must be the maximum element in the array. Otherwise, if an element has won consecutively $k$ times, then this element is the final winner.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        mx = arr[0]
        cnt = 0
        for x in arr[1:]:
            if mx < x:
                mx = x
                cnt = 1
            else:
                cnt += 1
            if cnt == k:
                break
        return mx

Continue Practicing

#1560 most visited sector in a circular track #1562 find latest group of size m #1503 last moment before all ants fall out of a plank