Find the Winner of an Array Game

Problem Statement

In this scenario, we're given an array arr composed of distinct integers and a number k. The task involves a sequential game conducted between the first two elements of the array: arr[0] and arr[1]. In each game round, the two elements are compared, and the larger one wins the round, maintaining its position at the start of the array, while the loser shifts to the array's end. This game persists until an integer secures k consecutive wins. The objective is to determine which integer will reach the mark of k consecutive wins first. Considering the array's elements are unique and the range of values within, there is an assurance of a definitive winner by the game's conclusion.

Examples

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

Approach and Intuition

The handling of the problem can be visualized as a process where iteratively the leading pair in the array contest and post their comparison, restructured based on the winner:

1. Initialize two counters: one for the current winner and another for the count of consecutive wins (current_winner and win_count).
2. As the larger of the first two elements becomes current_winner, compare it with the next in line. If current_winner prevails, increment win_count; otherwise, reset win_count to 1.
3. The key observation is the potential domination by a particularly large number, reducing the need for many comparisons once it has its first win, simplifying the process:
   • If k is exceedingly large but there exists one very large element in the array, after it moves to the front due to an initial victory, it will continue winning against all subsequent smaller numbers.
   • This cycle might only need to revisit comparisons when the element current_winner is minuscule relative to k. Still, since it shifts outer competitors (lower values) successively to the array's end, rare is the occasion for extended series of evaluations.
4. Therefore, an optimal approach utilizes direct pairwise comparisons without explicit full array rotations, and the algorithm significantly abbreviates when current_winner consecutively defeats k-1 challengers.

In essence, the approach utilizes a queue-like behavior without actual queue operations by manipulating array indices and element monitoring, ensuring efficiency even as input constraints extend to larger sizes and values.

Solutions

class Solution {
public:
    int determineWinner(vector<int>& nums, int k) {
        int highest = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            highest = max(highest, nums[i]);
        }
            
        int current = nums[0];
        int consecutiveWins = 0;
            
        for (int i = 1; i < nums.size(); i++) {
            int nextCompetitor = nums[i];
                
            if (current > nextCompetitor) {
                consecutiveWins++;
            } else {
                current = nextCompetitor;
                consecutiveWins = 1;
            }
                
            if (consecutiveWins == k || current == highest) {
                return current;
            }
        }
            
        return -1;
    }
};