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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Winner of an Array Game

Number: 1657

Difficulty: Medium

Paid? No

Companies: Adobe, Directi

Problem Description

Given an integer array of distinct integers and an integer k, simulate a game where the first two elements compete. In each round, the larger integer remains at the front (position 0) and its win streak increases by 1, while the smaller integer moves to the end of the array. The game ends when one integer wins k consecutive rounds. Return that integer.

Key Insights

  • The simulation compares the current winner with the next challenger.
  • If the current winner beats the challenger, its win count increases; otherwise, the challenger becomes the new current winner with a win count of 1.
  • Once the maximum element becomes the current winner, it will win every subsequent game. Thus, if k is very large (k ≥ n-1), the maximum element is the answer.
  • By leveraging this observation, we can avoid an overly long simulation when k is large.

Space and Time Complexity

Time Complexity: O(n) in the worst-case scenario when k < n (each element participates in comparisons until a winner is determined).
Space Complexity: O(n) due to the use of a queue (deque) for simulation.

Solution

The approach is to simulate the game using a queue (deque). We initialize the first element as the current winner with a consecutive win count set to 0. Then, for each round, we:

  • Compare the current winner with the next challenger.
  • If the current winner wins, we increment the win count and move the challenger to the end of the queue.
  • If the challenger wins, it becomes the new current winner with a win count of 1, and the former winner is appended to the end.
  • The process repeats until the current winner achieves k consecutive wins. Additionally, if k is greater than or equal to n-1 (where n is the length of the array), the maximum value in the array will eventually win, so we can return that immediately.

Code Solutions

from collections import deque

def find_winner(arr, k):
    # Shortcut: if k is large enough, the maximum element wins
    if k >= len(arr) - 1:
        return max(arr)
    
    # Initialize deque with array elements
    dq = deque(arr)
    # Set initial current winner and win count
    current_winner = dq.popleft()
    win_count = 0
    
    # Simulate the game until one wins k consecutive rounds.
    while win_count < k:
        # Get the next challenger
        challenger = dq.popleft()
        if current_winner > challenger:
            # Current winner wins this round
            win_count += 1
            # Append the challenger to the end of the deque
            dq.append(challenger)
        else:
            # Challenger wins, becomes the new current winner
            dq.append(current_winner)
            current_winner = challenger
            # Reset win count since a new number has started winning
            win_count = 1
    return current_winner

# Example usage:
# print(find_winner([2,1,3,5,4,6,7], 2))  # Expected output: 5
← Back to All Questions