Find the Winner of an Array Game

Med

#1414Time: O(N), where N is the number of elements in the array. Although the game could theoretically run for many rounds, any element can only be moved to the back after losing. The maximum element in the array will eventually become the champion and will never lose again. It takes at most O(N) rounds for this to happen. Each round involves constant-time deque operations.Space: O(N), where N is the number of elements in the array. This is because we use a `Deque` to store all the elements.1 company

Data structures

Array

Companies

Directi

Prompt

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 <= 10⁵
1 <= arr[i] <= 10⁶
arr contains distinct integers.
1 <= k <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the game process as described in the problem. We use a data structure that supports efficient removal from the front and addition to the back, such as a Deque (Double-Ended Queue). This allows us to model the game where the loser of a round moves to the end of the array.

Algorithm

Convert the input array arr into a Deque (Double-Ended Queue) to efficiently simulate the movement of elements.
Initialize current_winner with the first element and win_count to 0.
Enter a loop that continues as long as win_count is less than k.
In each iteration, take the next element from the front of the deque as the challenger.
Compare current_winner with the challenger.
If current_winner wins, increment win_count and add the challenger to the back of the deque.
If challenger wins, it becomes the new current_winner, win_count is reset to 1, and the old winner is added to the back of the deque.
The loop terminates when a player achieves k consecutive wins, and we return that player.

Walkthrough

We begin by populating a Deque with all the elements from the input array arr. The first element of the deque is designated as the initial current_winner, and its win count is initialized to zero. The simulation proceeds in rounds within a loop. In each round, the element at the front of the deque (the challenger) is compared against the current_winner. If the current_winner is larger, its win streak (win_count) is incremented, and the challenger is moved to the end of the deque. If the challenger is larger, it becomes the new current_winner, its win count is set to 1, and the former winner is sent to the end of the deque. This process continues until a player's win_count reaches k. The problem guarantees a winner, ensuring the loop will terminate. The largest element in the array will eventually become the champion and will never be defeated, so the simulation will take at most O(N) rounds.

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public int getWinner(int[] arr, int k) {6        // Optimization: If k is large, the max element will win.7        if (k >= arr.length) {8            int maxVal = 0;9            for (int num : arr) {10                maxVal = Math.max(maxVal, num);11            }12            return maxVal;13        }14 15        Deque<Integer> deque = new ArrayDeque<>();16        for (int num : arr) {17            deque.add(num);18        }19 20        int currentWinner = deque.pollFirst();21        int winCount = 0;22 23        // The game is guaranteed to have a winner.24        while (winCount < k) {25            int challenger = deque.pollFirst();26            if (currentWinner > challenger) {27                winCount++;28                deque.addLast(challenger);29            } else {30                deque.addLast(currentWinner);31                currentWinner = challenger;32                winCount = 1;33            }34        }35        return currentWinner;36    }37}

Complexity

Time

O(N), where N is the number of elements in the array. Although the game could theoretically run for many rounds, any element can only be moved to the back after losing. The maximum element in the array will eventually become the champion and will never lose again. It takes at most O(N) rounds for this to happen. Each round involves constant-time deque operations.

Space

O(N), where N is the number of elements in the array. This is because we use a `Deque` to store all the elements.

Trade-offs

Pros

The logic is a direct and intuitive translation of the problem statement, making it easy to understand.
Correctly simulates the game mechanics for all valid inputs.

Cons

Requires O(N) extra space to store the elements in a deque, which is less memory-efficient than an in-place solution.

A more efficient approach avoids the need for an auxiliary data structure by recognizing that the game can be simulated in a single pass over the array. We only need to keep track of the current champion and its number of consecutive wins. The rest of the array can be treated as a queue of upcoming challengers.

Algorithm

Initialize current_winner as arr[0] and win_count as 0.
Iterate through the array starting from the second element (i = 1).
In each iteration, compare current_winner with the challenger arr[i].
If current_winner is greater, increment win_count.
If arr[i] is greater, it becomes the new current_winner, and win_count is reset to 1.
After each comparison, check if win_count equals k. If it does, return current_winner.
If the loop completes without returning, the final current_winner must be the largest element in the array and is the guaranteed winner. Return current_winner.

Walkthrough

This optimized method iterates through the array just once. We designate arr[0] as the initial current_winner and initialize its win_count to 0. Then, we loop from arr[1] to the end of the array. Each element arr[i] challenges the current_winner. If the current_winner wins, we increment its win_count. If the challenger arr[i] wins, it becomes the new current_winner, and we reset its win_count to 1. At each step, we check if the win_count has reached k. If so, we have found our winner and can return it immediately. A key insight is that if we finish the pass without win_count reaching k, the current_winner at that point must be the largest element in the entire array. This is because any smaller element that temporarily became the winner would have been defeated by a larger one later in the array. This largest element will never be defeated again and is thus the guaranteed winner of the game.

1class Solution {2    public int getWinner(int[] arr, int k) {3        // If k is 1, the winner is simply the larger of the first two elements.4        if (k == 1) {5            return Math.max(arr[0], arr[1]);6        }7        // If k is greater than or equal to the array length, the largest element will win.8        if (k >= arr.length) {9            int maxVal = 0;10            for (int num : arr) {11                maxVal = Math.max(maxVal, num);12            }13            return maxVal;14        }15 16        int currentWinner = arr[0];17        int winCount = 0;18 19        for (int i = 1; i < arr.length; i++) {20            if (currentWinner > arr[i]) {21                winCount++;22            } else {23                currentWinner = arr[i];24                winCount = 1;25            }26 27            if (winCount == k) {28                return currentWinner;29            }30        }31 32        // If the loop completes, the currentWinner is the maximum element in the array,33        // and it will be the ultimate winner.34        return currentWinner;35    }36}

Complexity

Time

O(N), where N is the number of elements in the array. We perform a single pass through the array, and each step takes constant time.

Space

O(1). We only use a few variables (`currentWinner`, `winCount`) to store the state, regardless of the input size.

Trade-offs

Pros

Extremely efficient, using only a single pass through the array.
Optimal space complexity, as it uses only a constant amount of extra space.
Simple to implement.

Cons

The reasoning for why the loop's final current_winner is the answer if k is not reached might be slightly less intuitive than a direct simulation.

Solutions

Solution

1public class Solution { public int GetWinner ( int [] arr , int k ) { int maxElement = arr [ 0 ], count = 0 ; for ( int i = 1 ; i < arr . Length ; i ++) { if ( maxElement < arr [ i ]) { maxElement = arr [ i ]; count = 1 ; } else { count ++; } if ( count == k ) { break ; } } return maxElement ; } }

1class Solution {2public3  int getWinner(int[] arr, int k) {4    int mx = arr[0];5    for (int i = 1, cnt = 0; i < arr.length; ++i) {6      if (mx < arr[i]) {7        mx = arr[i];8        cnt = 1;9      } else {10        ++cnt;11      }12      if (cnt == k) {13        break;14      }15    }16    return mx;17  }18}

1class Solution {2public:3  int getWinner(vector<int> &arr, int k) {4    int mx = arr[0];5    for (int i = 1, cnt = 0; i < arr.size(); ++i) {6      if (mx < arr[i]) {7        mx = arr[i];8        cnt = 1;9      } else {10        ++cnt;11      }12      if (cnt == k) {13        break;14      }15    }16    return mx;17  }18};

1class Solution:2    def getWinner(self, arr: List[int], k: int) -> int: mx = arr[0] cnt = 0 for x in arr[1:]: if mx < x: mx = x cnt = 1 else: cnt += 1 if cnt == k: break return mx

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem