Find the Winner of an Array Game
Asked at Goldman Sachs
Problem
Find the Winner of an Array Game repeatedly compares the first two elements of an array: the larger stays in front and the smaller moves to the back. The game ends when one element wins k rounds in a row. Simulating the queue literally is slow when k is huge, but a single pass is enough.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Literal simulation with a queue can take up to k rounds, and k can be 10^9.
Key insight: the current champion faces the remaining elements in their original order. Losers go to the back and never matter again until the champion has beaten everyone.
So scan once: keep champ and wins. For each next element, if it is larger it becomes champion with 1 win; otherwise the champion gains a win. Stop when wins == k.
If the scan finishes without reaching k wins, the champion is the array maximum — it will win every future round, so it wins eventually.
Walkthrough: [2,1,3,5,4,6,7], k = 2: 2 beats 1 (1 win), 3 beats 2 (1 win), 5 beats 3 (1), 5 beats 4 (2 wins) -> answer 5.
Optimal Approach
Step 1: champ = arr[0], wins = 0.
Step 2: For each x in arr[1:]:
If x > champ: champ = x, wins = 1.
Else: wins += 1.
If wins == k, return champ.
Step 3: Return champ (the maximum).
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Simulating with a deque until someone reaches k wins. With k = 10^9 that never finishes.
Starting the new champion's streak at 0 instead of 1 — beating the previous champion counts as a win.
Not explaining why the maximum wins if no one reaches k during the scan.
Using >= when comparing values; all values are distinct, but a strict comparison matches the rules.
Solution Code
def getWinner(arr, k):
champ = arr[0]
wins = 0
for x in arr[1:]:
if x > champ:
champ = x
wins = 1
else:
wins += 1
if wins == k:
return champ
return champFrequently Asked Questions
What is the Find the Winner of an Array Game problem?
Find the Winner of an Array Game repeatedly compares the first two elements of an array: the larger stays in front and the smaller moves to the back. The game ends when one element wins `k` rounds in a row. Simulating the queue literally is slow when `k` is huge, but a single pass is enough.
How do you solve Find the Winner of an Array Game?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Find the Winner of an Array Game?
Find the Winner of an Array Game is asked at Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Find the Winner of an Array Game?
- Simulating with a deque until someone reaches `k` wins. With `k = 10^9` that never finishes.
- Starting the new champion's streak at 0 instead of 1 — beating the previous champion counts as a win.
- Not explaining why the maximum wins if no one reaches `k` during the scan.
- Using `>=` when comparing values; all values are distinct, but a strict comparison matches the rules.