Given an integer array arr of distinct integers and an integer k.
A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0, and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.
Return the integer which will win the game.
It is guaranteed that there will be a winner of the game.
Example 1:
Input: arr = [2,1,3,5,4,6,7], k = 2 Output: 5 Explanation: 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 Explanation: 3 will win the first 10 rounds consecutively.
Constraints:
2 <= arr.length <= 1051 <= arr[i] <= 106arr contains distinct integers.1 <= k <= 109In #1535 Find the Winner of an Array Game, elements compete in rounds where the first two numbers are compared and the larger value stays at the front while the smaller moves to the end. The winner is the element that achieves k consecutive wins.
A direct simulation using a queue or array rotation works but can be inefficient for large inputs. A better observation is that the current strongest element behaves like a champion. While scanning the array from left to right, compare each value with the current champion. If the champion wins, increment its win streak; if it loses, the new element becomes the champion and the streak resets.
The process stops once a number reaches k consecutive wins. Additionally, if k is larger than the array length, the maximum element will inevitably become the winner. This leads to a linear scan approach with O(n) time and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Queue/Direct Simulation | O(n + k) | O(n) |
| Optimized Champion Scan | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
If k ≥ arr.length return the max element of the array.
If k < arr.length simulate the game until a number wins k consecutive games.
This approach involves simulating the game as described. In each round, compare the first two elements. The larger element stays at the front, while the smaller one is moved to the end. Track the number of consecutive wins for the current maximum element. The game terminates once an element wins k consecutive games, or we can conclude the maximum element will always win once it has dominated for enough rounds due to its magnitude relative to other elements.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we use only constant space.
1def get_winner(arr, k):
2 max_num = arr[0]
3 win_count = 0
4 for num in arr[1:]:
5
In this Python code, we maintain the current maximum and its consecutive winning streak. Iterate through each element, compare, and update if necessary. As soon as a number wins k consecutive rounds, return it as the winner.
This variant uses a concept very similar to the simulation approach but adds a breaking condition for improved efficiency. It exploits the game's characteristics by noting if the current maximum wins continuously even before counting to k, it will naturally reach the conclusion. This allows early termination if the maximum element becomes apparent quickly.
Time Complexity: O(n), potentially terminating faster.
Space Complexity: O(1).
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
If k is greater than or equal to the array length, the maximum element in the array will always become the winner. This is because no smaller element can beat it enough times to stop its streak.
Yes, this problem is commonly used in coding interviews to test simulation skills and the ability to optimize with observations. Interviewers often expect candidates to move from naive simulation to a linear scan approach.
Although the game can be simulated with a queue or deque, an optimized solution only requires basic array traversal and a few variables. This reduces extra memory usage and keeps the algorithm efficient.
The optimal approach tracks the current champion while scanning the array. Each new element challenges the champion, and the win counter increases or resets accordingly. The process stops once an element reaches k consecutive wins or when the maximum element is guaranteed to win.
Enhancing Python code with strategic exit, it estimates remaining rounds against advantageous maximum, ceasing prematurely if ongoing dominance is logically assertable.