Watch 10 video solutions for Find the Winner of an Array Game, a medium level problem involving Array, Simulation. This walkthrough by codestorywithMIK has 4,569 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: You are given an integer array where the first two elements compete in rounds. The larger value wins and stays at the front, while the smaller moves to the end. The first number that wins k consecutive rounds becomes the winner. The task is to simulate this process and return the winning element.
Approach 1: Simulated Rounds Approach (O(n * k) time, O(n) space)
This method directly simulates the rules of the game using a queue-like process. Compare the first two elements, move the smaller value to the end, and keep the larger value at the front while tracking consecutive wins. Each round performs constant operations but can repeat many times if k is large. A queue or simple array rotation can model the process. This approach mirrors the problem description exactly and is useful for understanding the mechanics of the game.
Approach 2: Break Condition Approach (O(n) time, O(1) space)
The key observation is that the largest number in the array will eventually dominate every comparison. Instead of fully simulating rotations, iterate once through the array while maintaining a current champion and its consecutive win count. If the next value is larger, it becomes the new champion and the streak resets. Otherwise the champion's win streak increases. Once the streak reaches k, you can stop early. If no element reaches k, the maximum element of the array becomes the winner by default.
This approach works because the champion only changes when a larger element appears, which can happen at most n times. It avoids repeated array rotations and keeps only two variables: the current winner and win count.
Recommended for interviews: The Break Condition Approach is what interviewers typically expect. It shows you recognized the core insight that the maximum element will eventually dominate and that full simulation is unnecessary. Mentioning the simulated approach first demonstrates understanding of the game rules, while optimizing to the linear scan shows algorithmic reasoning. The problem mainly tests understanding of array traversal and efficient simulation patterns commonly used in competitive coding.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Rounds Approach | O(n * k) | O(n) | When implementing the game rules exactly or demonstrating a straightforward simulation. |
| Break Condition Approach | O(n) | O(1) | Best for interviews and large inputs since it avoids repeated rotations and stops early when a champion reaches k wins. |