Problem Description

You're given an array arr of distinct integers and an integer k. A game is played with the following rules:

1. Start with the first two elements of the array (arr[0] and arr[1])
2. In each round, compare these two elements:
   • The larger integer wins and stays at position 0
   • The smaller integer moves to the end of the array
3. The game continues with the winner at position 0 facing the next element (now at position 1)
4. The game ends when an integer wins k consecutive rounds

Your task is to find which integer will win the game.

For example, if arr = [2, 1, 3, 5, 4, 6, 7] and k = 2:

• Round 1: Compare 2 and 1 → 2 wins (1 win for 2), array becomes [2, 3, 5, 4, 6, 7, 1]
• Round 2: Compare 2 and 3 → 3 wins (1 win for 3), array becomes [3, 5, 4, 6, 7, 1, 2]
• Round 3: Compare 3 and 5 → 5 wins (1 win for 5), array becomes [5, 4, 6, 7, 1, 2, 3]
• Round 4: Compare 5 and 4 → 5 wins (2 wins for 5)
• Since 5 has won 2 consecutive rounds, the game ends and 5 is the winner

The problem guarantees that there will always be a winner.

Intuition

The key insight is recognizing that we don't actually need to simulate moving elements to the end of the array. Let's think about what really happens during the game:

When two elements compare, the winner stays at position 0 and faces the next element. The loser goes to the end, but here's the crucial observation: once an element loses, it can only win again if it eventually faces all other elements and beats them all. This means it would need to beat the current champion who has been winning.

Consider what happens as the game progresses:

• The winner at position 0 keeps facing new challengers one by one
• Each element in the array gets exactly one chance to challenge the current champion (except for the initial element at position 0)
• If we've gone through all n-1 other elements without anyone winning k times, the current champion must be the maximum element of the array

This leads to an important realization: the maximum element of the array will eventually win if the game goes on long enough, because it can never lose to any other element.

Therefore, we have two scenarios:

1. Some element wins k consecutive rounds before we go through the entire array
2. We go through the entire array without anyone winning k times, in which case the maximum element must be the winner

This means we can simply iterate through the array once, keeping track of:

• The current "champion" (the element that would be at position 0)
• How many consecutive wins the current champion has

If the champion reaches k wins, they're our answer. Otherwise, after going through all elements, the current champion (which would be the maximum element) is our answer.

Solution Approach

Based on our intuition, we can implement a simple linear scan without actually simulating the array rotations:

1. Initialize tracking variables:

   • mx: The current champion (initially arr[0])
   • cnt: The consecutive win count for the current champion (initially 0)

2. Iterate through the array starting from index 1:

   • For each element x in arr[1:]:
     • Compare with current champion:
       • If mx < x: The challenger wins
         • Update mx = x (new champion)
         • Reset cnt = 1 (first win for new champion)
       • If mx >= x: The champion wins
         • Increment cnt += 1 (another consecutive win)
     • Check winning condition:
       • If cnt == k: We found our winner, break early

3. Return the champion mx

The beauty of this approach is that even if we iterate through all n-1 elements without anyone achieving k consecutive wins, the variable mx will hold the maximum element of the array, which is guaranteed to be the eventual winner.

Why this works:

• Each element gets exactly one chance to challenge the current champion during our iteration
• If an element becomes the new champion, it faces all subsequent elements in order
• If we complete the iteration without reaching k wins, the current champion has already beaten all other elements at least once, making it the maximum element
• The maximum element will continue winning indefinitely if the game continues

Time Complexity: O(n) where n is the length of the array - we iterate through the array at most once.

Space Complexity: O(1) - we only use a constant amount of extra space for tracking variables.

Example Walkthrough

Let's walk through a small example with arr = [3, 2, 1, 4] and k = 2:

Initial Setup:

• mx = 3 (first element becomes initial champion)
• cnt = 0 (no wins yet)

Iteration 1: Compare 3 vs 2

• Since mx (3) > 2, the champion wins
• cnt = 1 (first win for 3)
• Check: cnt (1) < k (2), continue

Iteration 2: Compare 3 vs 1

• Since mx (3) > 1, the champion wins again
• cnt = 2 (second consecutive win for 3)
• Check: cnt (2) == k (2), we found our winner!
• Return 3

Let's verify this matches the actual game simulation:

• Round 1: [3, 2, 1, 4] → 3 beats 2 → [3, 1, 4, 2]
• Round 2: [3, 1, 4, 2] → 3 beats 1 → [3, 4, 2, 1]
• 3 has won 2 consecutive rounds, so 3 wins!

Another example with arr = [1, 5, 2, 3] and k = 3:

Initial Setup:

• mx = 1 (first element)
• cnt = 0

Iteration 1: Compare 1 vs 5

• Since mx (1) < 5, challenger wins
• mx = 5 (new champion)
• cnt = 1 (first win for 5)
• Check: cnt (1) < k (3), continue

Iteration 2: Compare 5 vs 2

• Since mx (5) > 2, champion wins
• cnt = 2 (second consecutive win for 5)
• Check: cnt (2) < k (3), continue

Iteration 3: Compare 5 vs 3

• Since mx (5) > 3, champion wins
• cnt = 3 (third consecutive win for 5)
• Check: cnt (3) == k (3), we found our winner!
• Return 5

Note how we never needed to actually move elements to the end of the array - we just tracked who the current champion is and their win streak!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array arr.

The algorithm iterates through the array once using a for loop that goes through arr[1:], which means it processes at most n-1 elements. Each iteration performs constant time operations (comparisons and variable updates). Even though there's a break statement when cnt == k, in the worst case scenario (when k is very large or when we need to find the maximum element), we still traverse the entire array. Therefore, the time complexity is linear with respect to the size of the input array.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space regardless of the input size. It maintains just two variables: mx (to store the current winner) and cnt (to count consecutive wins). The iteration through arr[1:] doesn't create a new array in Python - it's just a slice that provides a view of the original array. No additional data structures are used that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding When k > n-1

The Issue: A common mistake is thinking we need to simulate the actual circular rotation of the array when k is larger than n-1. Developers might implement complex logic to handle the case where elements cycle back to the front of the array after being moved to the end.

Why It's Wrong: Consider arr = [3, 2, 1] with k = 10. After the first pass:

• 3 beats 2 (1 win)
• 3 beats 1 (2 wins)
• Now 3 is the maximum element

Even though k = 10 > 2, we don't need to continue simulating. Once an element has beaten all others (becoming the maximum), it will continue winning indefinitely. The maximum element will never lose, so it's guaranteed to reach k consecutive wins.

The Solution: The provided code handles this elegantly by:

1. Finding the maximum element through one pass
2. If no element reaches k wins during the pass, the current winner is the maximum
3. The maximum element is automatically returned as the winner

Pitfall 2: Off-by-One Error in Initial Win Count

The Issue: When implementing the solution, developers might incorrectly initialize the win count:

# Incorrect approach
current_winner = arr[0]
consecutive_wins = 1  # Wrong! arr[0] hasn't won anything yet

for current_element in arr[1:]:
    if current_winner < current_element:
        current_winner = current_element
        consecutive_wins = 1
    else:
        consecutive_wins += 1

Why It's Wrong: This gives arr[0] credit for a win it hasn't earned yet. If k = 1 and arr[0] is larger than arr[1], this would incorrectly return arr[0] after just one comparison instead of requiring it to actually win one round.

The Solution: Always initialize consecutive_wins = 0 because the first element hasn't competed yet. It only gets wins by actually beating other elements in comparisons.

Pitfall 3: Attempting to Actually Rotate the Array

The Issue: Some implementations try to physically manipulate the array:

# Inefficient approach
while True:
    if arr[0] > arr[1]:
        winner = arr[0]
        loser = arr.pop(1)
        arr.append(loser)
        wins += 1
    else:
        winner = arr[1]
        loser = arr.pop(0)
        arr.append(loser)
        arr[0] = winner
        wins = 1
  
    if wins == k:
        return winner

Why It's Wrong:

• Time complexity becomes O(n*k) in worst case due to array manipulations
• Space complexity increases due to array modifications
• Unnecessarily complex and prone to bugs

The Solution: The linear scan approach simulates the game conceptually without actually moving elements. Each element gets exactly one chance to challenge the current champion, which perfectly mirrors what would happen in the actual game rotation.