Problem Description

Given an integer array arr of distinct integers and an integer k, a game is played as follows:

• At each round, compare the first two elements of the array.
• The larger of the two wins and stays at the front, while the smaller is moved to the end of the array.
• The winner's consecutive win count increases by 1 for every round they win.
• The game ends when an element achieves k consecutive wins.
• Return the value of the element that first achieves k consecutive wins.

Constraints:

• There is always at least one valid solution.
• Elements are not reused except by being moved to the end of the array.
• arr contains unique elements.

Thought Process

The first idea that comes to mind is to simulate the game exactly as described: repeatedly compare the first two elements, update the win count, and move the loser to the end. This brute-force approach is straightforward but could be inefficient for large arrays or large k, as it may involve a lot of unnecessary moves, especially if the largest element is at the end.

However, since the largest element cannot be beaten by any other element, it will eventually accumulate k consecutive wins if k is large enough. This insight allows us to optimize: we don't have to simulate all moves if we can keep track of the current winner and their streak.

The challenge is to efficiently track the current winner and their consecutive wins without moving elements unnecessarily.

Solution Approach

Let's break down the optimized approach step-by-step:

1. Initialize:
   • Set the first element of arr as the current winner.
   • Initialize a counter for consecutive wins.
2. Iterate through the array:
   • For each subsequent element, compare it with the current winner.
   • If the current winner is greater, increment their win streak.
   • If the challenger is greater, they become the new winner and their streak resets to 1.
3. Check the win condition:
   • If the current winner's streak reaches k, return them immediately.
   • If the iteration completes and no one reaches k (possible if k is large), return the array's maximum element (as it cannot be beaten).

This approach uses a single pass through the array and avoids unnecessary rotations or full simulation, making it efficient.

Example Walkthrough

Let's consider the input arr = [2,1,3,5,4,6,7] and k = 2.

1. Round 1: Compare 2 and 1. 2 wins (streak: 1). Array: [2,3,5,4,6,7,1]
2. Round 2: Compare 2 and 3. 3 wins (streak: 1). Array: [3,5,4,6,7,1,2]
3. Round 3: Compare 3 and 5. 5 wins (streak: 1). Array: [5,4,6,7,1,2,3]
4. Round 4: Compare 5 and 4. 5 wins (streak: 2). Now 5 has 2 consecutive wins, matching k.

The function returns 5 as the winner.

Time and Space Complexity

• Brute-force approach:
  • Time: O(nk), because each round could involve up to n moves and up to k rounds.
  • Space: O(n), for storing the array.
• Optimized approach:
  • Time: O(n), since we traverse the array at most once.
  • Space: O(1), as we only track a few variables for the current winner and streak.

The optimized approach is much more efficient, especially for large values of n and k.

Code Implementation

def getWinner(arr, k):
    winner = arr[0]
    streak = 0
    for i in range(1, len(arr)):
        if arr[i] > winner:
            winner = arr[i]
            streak = 1
        else:
            streak += 1
        if streak == k:
            return winner
    return winner
      

int getWinner(vector<int>& arr, int k) {
    int winner = arr[0];
    int streak = 0;
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > winner) {
            winner = arr[i];
            streak = 1;
        } else {
            ++streak;
        }
        if (streak == k) return winner;
    }
    return winner;
}
      

public int getWinner(int[] arr, int k) {
    int winner = arr[0];
    int streak = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > winner) {
            winner = arr[i];
            streak = 1;
        } else {
            streak++;
        }
        if (streak == k) return winner;
    }
    return winner;
}
      

var getWinner = function(arr, k) {
    let winner = arr[0];
    let streak = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > winner) {
            winner = arr[i];
            streak = 1;
        } else {
            streak++;
        }
        if (streak === k) return winner;
    }
    return winner;
};
      

Summary

The key insight in this problem is that the largest element will always eventually win if k is large. By tracking only the current winner and their consecutive wins, we avoid unnecessary array operations and achieve a linear time solution. This approach is both simple and efficient, making use of the problem's constraints and properties for an elegant solution.