Find the Winner of an Array Game — Problem & Solution
Find the Winner of an Array Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Winner of an Array Game is a medium coding problem on arrays and simulation, asked in Amazon, Google, Microsoft and Directi interviews.
- Difficulty: Medium
- Topics: Arrays, Simulation
- Asked at: Amazon, Google, Microsoft, Directi
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr holds distinct integers. Repeatedly compare arr[0] with arr[1]: the larger stays at position 0 and the smaller is moved to the end of the array.
Return the first integer to win k consecutive rounds.
Example 1
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: 5 takes the front by beating 3, then beats 4 — two rounds in a row.
Example 2
Input: arr = [3,2,1], k = 10
Output: 3
Explanation: Once the maximum reaches the front it wins every round, so it wins any `k`.
Example 3
Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99
Constraints
2 <= arr.length <= 10^51 <= arr[i] <= 10^6arr contains distinct integers.1 <= k <= 10^9
Hints for Find the Winner of an Array Game
Hint 1
Never simulate the rotation —
kcan be a billion.Hint 2
One pass is enough: carry the current champion and a streak counter.
Hint 3
If nobody reaches
kduring that pass, the array maximum has reached the front and wins forever.
How to solve Find the Winner of an Array Game
Sweep once, carrying the current champion and its consecutive-win count. A larger element takes over with a streak of 1; anything smaller extends the streak. If the streak reaches k, that element is the answer; otherwise the maximum has surfaced and wins every round from then on.
Approach
- Start with
cur = arr[0]andwins = 0. - For each later element: if it is larger, it becomes
curwithwins = 1; otherwise incrementwins. - Return
curas soon aswins == k. - After the sweep, return
cur— by then it is the array maximum.
Why it works
The rotation never needs to be simulated because the elements pushed to the back are, in order, exactly the ones the sweep has already passed — so the first pass sees every challenger in the order it would arrive. And once the maximum is at the front nothing can dislodge it, so a k larger than the array is answered by the maximum without any extra work.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
kcan exceed the array length, so a simulation must be bounded or avoided.- A new champion starts its streak at 1 — it just won a round.
- The elements are distinct, so there are no ties to resolve.
Reference solution
Python
from typing import List
def getWinner(arr: List[int], k: int) -> int:
cur, wins = arr[0], 0
for v in arr[1:]:
if v > cur:
cur, wins = v, 1
else:
wins += 1
if wins == k:
return cur
return curJava
public static int getWinner(int[] arr, int k) {
int cur = arr[0], wins = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > cur) {
cur = arr[i];
wins = 1;
} else {
wins++;
}
if (wins == k) return cur;
}
return cur;
}C++
int getWinner(vector<int>& arr, int k) {
int cur = arr[0], wins = 0;
for (size_t i = 1; i < arr.size(); i++) {
if (arr[i] > cur) {
cur = arr[i];
wins = 1;
} else {
wins++;
}
if (wins == k) return cur;
}
return cur;
}JavaScript
var getWinner = function(arr, k) {
var cur = arr[0], wins = 0;
for (var i = 1; i < arr.length; i++) {
if (arr[i] > cur) { cur = arr[i]; wins = 1; } else wins++;
if (wins === k) return cur;
}
return cur;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays