MediumArraySimulationUpdated Sep 2026

1535. Find the Winner of an Array Game

Asked at Goldman Sachs

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array arr of distinct integers and an integer k. A game runs on this array.

In each round, compare the first two elements, arr[0] and arr[1]. The larger one wins and stays at index 0. The smaller one is moved to the end of the array. All other elements shift one position to the left.

The game stops as soon as some integer has won k rounds in a row (not k total wins). Return that integer. It is guaranteed that the game always ends with a winner.

The game rules

21354670123456Round 1: 2 vs 1 — 2 wins and stays at index 0235467101234561 moves to the end; now 2 faces 3 in round 2
The bigger of the first two elements stays in front; the smaller one is sent to the back of the line.

Constraints

  • ●2 <= arr.length <= 10^5
  • ●1 <= arr[i] <= 10^6
  • ●arr contains distinct integers
  • ●1 <= k <= 10^9

Examples

Example 1
Inputarr = [2,1,3,5,4,6,7], k = 2
Output5
WhyRound 1: 2 beats 1, so 2 has 1 win. Round 2: 2 beats 3? No — 3 is bigger, so 3 wins and gets 1 win. Round 3: 3 vs 5, 5 wins, 1 win. Round 4: 5 vs 4, 5 wins again, now 2 wins in a row. The game stops and the answer is 5.
Example 2
Inputarr = [3,2,1], k = 10
Output3
Why3 beats 2, then 3 beats 1, and after that 3 keeps facing the same smaller numbers forever. It reaches 10 consecutive wins, so 3 is the winner.

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Literal simulation with a queue can take up to k rounds, and k can be 10^9.

2

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.

3

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.

4

If the scan finishes without reaching k wins, the champion is the array maximum — it will win every future round, so it wins eventually.

5

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).

One pass, no real queue

21354670123456nextStart: champ = 2, wins = 0. Next is 1, which is smaller,so wins = 121354670123456next3 beats 2, so champ = 3 with wins = 1. Then 5 beats 3,champ = 5, wins = 1213546701234565 beats 4, so wins = 2 = k. The answer is 5if x > champ: champ = x, wins = 1else: wins += 1stop when wins == k, else return max
Only the champion and its streak matter. Each new element either takes over or feeds the streak.
ComplexityTime O(n)Space O(1)One pass over the array, keeping only the current champion and its win streak.

What Trips People Up in Real Interviews

1

Simulating with a deque until someone reaches k wins. With k = 10^9 that never finishes.

2

Starting the new champion's streak at 0 instead of 1 — beating the previous champion counts as a win.

3

Not explaining why the maximum wins if no one reaches k during the scan.

4

Using >= when comparing values; all values are distinct, but a strict comparison matches the rules.

Solution Code

O(n) time
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 champ

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.