We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Winner of an Array Game

Difficulty: Medium

Problem Description

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.

Key Insights

  • The game is played between the first two elements of the array.
  • The winner of each round is determined by comparing the two integers.
  • The winner remains at position 0, while the loser is moved to the end of the array.
  • The game continues until one of the integers wins k consecutive rounds.
  • The constraints ensure that a winner is guaranteed, meaning the game will always end.

Space and Time Complexity

Time Complexity: O(n) - each element is processed a limited number of times. Space Complexity: O(1) - only a few variables are used for counting and tracking the winner.

Solution

To solve this problem, we can simulate the game using a queue-like approach. We will keep track of the current winner and their win count. We will continuously compare the two integers at the front of the array, update the winner, and move the loser to the end. If the current winner's win count reaches k, we return that integer as the winner. The algorithm primarily uses a loop and simple comparisons.

Code Solutions

def findTheWinner(arr, k):
    winner = arr[0]
    win_count = 0
    index = 1

    while True:
        if winner > arr[index]:
            win_count += 1
            index += 1
            if win_count == k:
                return winner
            if index == len(arr):
                index = 1  # Reset index to the second element
        else:
            win_count = 1  # Reset win count for the new winner
            winner = arr[index]
            index += 1
            if index == len(arr):
                index = 1  # Reset index to the second element
← Back to All Questions