{x}
blog image

Find the Winner of an Array Game

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

Solution Explanation for Find the Winner of an Array Game

This problem describes a game where two elements of an array are compared, the larger one wins and stays at the beginning, and the smaller one moves to the end. The game continues until one element wins k consecutive rounds. The goal is to find the ultimate winner.

Approach

A naive approach would be to simulate the game step-by-step. However, a more efficient approach recognizes a crucial observation: The winner will always be the largest element in the array unless an element wins k consecutive rounds before the largest element gets a chance.

Therefore, we can iterate through the array, keeping track of the current largest element (mx) seen so far and a counter (cnt) for consecutive wins of the current largest element.

  1. Initialize mx to the first element of the array and cnt to 0.
  2. Iterate through the remaining elements of the array.
  3. If the current element is greater than mx, it becomes the new mx, and cnt is reset to 1.
  4. If the current element is less than or equal to mx, increment cnt.
  5. If cnt reaches k, we've found the winner, and we can return mx.
  6. If the loop completes without cnt reaching k, the largest element in the array (mx) is the winner.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the array. In the worst case, we iterate through the entire array. The algorithm avoids simulating multiple rounds unnecessarily.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space to store mx and cnt.

Code Implementation (Python)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        mx = arr[0]  # Initialize the current largest element
        cnt = 0      # Initialize the consecutive win counter
        for x in arr[1:]: # Iterate from the second element
            if mx < x:   # If a larger element is found
                mx = x   # Update the largest element
                cnt = 1  # Reset the counter
            else:
                cnt += 1 # Increment the counter
            if cnt == k: # Check if k consecutive wins are achieved
                break     # If yes, break the loop
        return mx       # Return the winner (either from k wins or the largest element)

The implementations in other languages (Java, C++, Go, TypeScript, C#) follow the same logic, with minor syntactic differences. The core idea remains the efficient iteration and early termination upon reaching k consecutive wins.