#1535 Find the Winner of an Array Game - Solution

Dashboard Questions Topics Companies Sheets

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⁹

Approach	Time Complexity	Space Complexity
Queue/Direct Simulation	O(n + k)	O(n)
Optimized Champion Scan	O(n)	O(1)

Solutions (12)

Simulated Rounds Approach

This approach involves simulating the game as described. In each round, compare the first two elements. The larger element stays at the front, while the smaller one is moved to the end. Track the number of consecutive wins for the current maximum element. The game terminates once an element wins k consecutive games, or we can conclude the maximum element will always win once it has dominated for enough rounds due to its magnitude relative to other elements.

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we use only constant space.

C C++Java Python C#JavaScript

1using System;
2
3public class Solution {
4    public int GetWinner(int[] arr, int k) {
5        int max = arr[0];
6        int winCount = 0;
7        foreach (var num in arr[1..]) {
8            if (max > num) {
9                winCount++;
10            } else {
11                max = num;
12                winCount = 1;
13            }
14            if (winCount == k) return max;
        }
        return max;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] arr = {2, 1, 3, 5, 4, 6, 7};
        int k = 2;
        Console.WriteLine($"Winner: {sol.GetWinner(arr, k)}");
    }
}

Explanation

This C# solution iterates through the provided array, keeping track of the highest number seen so far and counting its consecutive wins. The process halts as soon as that number has won k rounds consecutively, returning as the game winner.

Break Condition Approach

This variant uses a concept very similar to the simulation approach but adds a breaking condition for improved efficiency. It exploits the game's characteristics by noting if the current maximum wins continuously even before counting to k, it will naturally reach the conclusion. This allows early termination if the maximum element becomes apparent quickly.

Time Complexity: O(n), potentially terminating faster.
Space Complexity: O(1).

C C++Java Python C#JavaScript

1
public class Solution {
    public int GetWinner(int[] arr, int k) {
        int max = arr[0];
        int winCount = 0;
        for (int i = 1; i < arr.Length; ++i) {
            if (max > arr[i]) {
                ++winCount;
            } else {
                max = arr[i];
                winCount = 1;
            }
            if (winCount == k || arr.Length - i <= winCount)
                return max;
        }
        return max;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] arr = {2, 1, 3, 5, 4, 6, 7};
        int k = 2;
        Console.WriteLine($"Winner: {sol.GetWinner(arr, k)}");
    }
}