Scale Engineer

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 <= 105
  • 1 <= arr[i] <= 106
  • arr contains distinct integers.
  • 1 <= k <= 109

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.

import java.util.ArrayDeque;import java.util.Deque; class Solution {    public int getWinner(int[] arr, int k) {        // Optimization: If k is large, the max element will win.        if (k >= arr.length) {            int maxVal = 0;            for (int num : arr) {                maxVal = Math.max(maxVal, num);            }            return maxVal;        }         Deque<Integer> deque = new ArrayDeque<>();        for (int num : arr) {            deque.add(num);        }         int currentWinner = deque.pollFirst();        int winCount = 0;         // The game is guaranteed to have a winner.        while (winCount < k) {            int challenger = deque.pollFirst();            if (currentWinner > challenger) {                winCount++;                deque.addLast(challenger);            } else {                deque.addLast(currentWinner);                currentWinner = challenger;                winCount = 1;            }        }        return currentWinner;    }}

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.

Solutions

public 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 ; } }

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 →

Next problem