# Find the Winner of an Array Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-winner-of-an-array-game)
Canonical: https://scaleengineer.com/dsa/problems/find-the-winner-of-an-array-game
**Data structures:** Array
**Companies:** [Directi](https://scaleengineer.com/companies/directi)
---
## Problem
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_.

It is **guaranteed** that there will be a winner of the game.

**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`

# Approaches
## Simulation with Deque
This approach directly simulates the game process as described in the problem. We use a data structure that supports efficient removal from the front and addition to the back, such as a `Deque` (Double-Ended Queue). This allows us to model the game where the loser of a round moves to the end of the array.
**Time:** O(N), where N is the number of elements in the array. Although the game could theoretically run for many rounds, any element can only be moved to the back after losing. The maximum element in the array will eventually become the champion and will never lose again. It takes at most O(N) rounds for this to happen. Each round involves constant-time deque operations. · **Space:** O(N), where N is the number of elements in the array. This is because we use a `Deque` to store all the elements.
**Pros:** The logic is a direct and intuitive translation of the problem statement, making it easy to understand.; Correctly simulates the game mechanics for all valid inputs.
**Cons:** Requires O(N) extra space to store the elements in a deque, which is less memory-efficient than an in-place solution.
### Explanation
We begin by populating a `Deque` with all the elements from the input array `arr`. The first element of the deque is designated as the initial `current_winner`, and its win count is initialized to zero. The simulation proceeds in rounds within a loop. In each round, the element at the front of the deque (the challenger) is compared against the `current_winner`. If the `current_winner` is larger, its win streak (`win_count`) is incremented, and the challenger is moved to the end of the deque. If the challenger is larger, it becomes the new `current_winner`, its win count is set to 1, and the former winner is sent to the end of the deque. This process continues until a player's `win_count` reaches `k`. The problem guarantees a winner, ensuring the loop will terminate. The largest element in the array will eventually become the champion and will never be defeated, so the simulation will take at most O(N) rounds.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int getWinner(int[] arr, int k) {
        // Optimization: If k is large, the max element will win.
        if (k >= arr.length) {
            int maxVal = 0;
            for (int num : arr) {
                maxVal = Math.max(maxVal, num);
            }
            return maxVal;
        }

        Deque<Integer> deque = new ArrayDeque<>();
        for (int num : arr) {
            deque.add(num);
        }

        int currentWinner = deque.pollFirst();
        int winCount = 0;

        // The game is guaranteed to have a winner.
        while (winCount < k) {
            int challenger = deque.pollFirst();
            if (currentWinner > challenger) {
                winCount++;
                deque.addLast(challenger);
            } else {
                deque.addLast(currentWinner);
                currentWinner = challenger;
                winCount = 1;
            }
        }
        return currentWinner;
    }
}
```
### Algorithm
- Convert the input array `arr` into a `Deque` (Double-Ended Queue) to efficiently simulate the movement of elements.
- Initialize `current_winner` with the first element and `win_count` to 0.
- Enter a loop that continues as long as `win_count` is less than `k`.
- In each iteration, take the next element from the front of the deque as the `challenger`.
- Compare `current_winner` with the `challenger`.
- If `current_winner` wins, increment `win_count` and add the `challenger` to the back of the deque.
- If `challenger` wins, it becomes the new `current_winner`, `win_count` is reset to 1, and the old winner is added to the back of the deque.
- The loop terminates when a player achieves `k` consecutive wins, and we return that player.

## Single Pass with Constant Space
A more efficient approach avoids the need for an auxiliary data structure by recognizing that the game can be simulated in a single pass over the array. We only need to keep track of the current champion and its number of consecutive wins. The rest of the array can be treated as a queue of upcoming challengers.
**Time:** O(N), where N is the number of elements in the array. We perform a single pass through the array, and each step takes constant time. · **Space:** O(1). We only use a few variables (`currentWinner`, `winCount`) to store the state, regardless of the input size.
**Pros:** Extremely efficient, using only a single pass through the array.; Optimal space complexity, as it uses only a constant amount of extra space.; Simple to implement.
**Cons:** The reasoning for why the loop's final `current_winner` is the answer if `k` is not reached might be slightly less intuitive than a direct simulation.
### Explanation
This optimized method iterates through the array just once. We designate `arr[0]` as the initial `current_winner` and initialize its `win_count` to 0. Then, we loop from `arr[1]` to the end of the array. Each element `arr[i]` challenges the `current_winner`. If the `current_winner` wins, we increment its `win_count`. If the challenger `arr[i]` wins, it becomes the new `current_winner`, and we reset its `win_count` to 1. At each step, we check if the `win_count` has reached `k`. If so, we have found our winner and can return it immediately. A key insight is that if we finish the pass without `win_count` reaching `k`, the `current_winner` at that point must be the largest element in the entire array. This is because any smaller element that temporarily became the winner would have been defeated by a larger one later in the array. This largest element will never be defeated again and is thus the guaranteed winner of the game.

```java
class Solution {
    public int getWinner(int[] arr, int k) {
        // If k is 1, the winner is simply the larger of the first two elements.
        if (k == 1) {
            return Math.max(arr[0], arr[1]);
        }
        // If k is greater than or equal to the array length, the largest element will win.
        if (k >= arr.length) {
            int maxVal = 0;
            for (int num : arr) {
                maxVal = Math.max(maxVal, num);
            }
            return maxVal;
        }

        int currentWinner = arr[0];
        int winCount = 0;

        for (int i = 1; i < arr.length; i++) {
            if (currentWinner > arr[i]) {
                winCount++;
            } else {
                currentWinner = arr[i];
                winCount = 1;
            }

            if (winCount == k) {
                return currentWinner;
            }
        }

        // If the loop completes, the currentWinner is the maximum element in the array,
        // and it will be the ultimate winner.
        return currentWinner;
    }
}
```
### Algorithm
- Initialize `current_winner` as `arr[0]` and `win_count` as 0.
- Iterate through the array starting from the second element (`i = 1`).
- In each iteration, compare `current_winner` with the challenger `arr[i]`.
- If `current_winner` is greater, increment `win_count`.
- If `arr[i]` is greater, it becomes the new `current_winner`, and `win_count` is reset to 1.
- After each comparison, check if `win_count` equals `k`. If it does, return `current_winner`.
- If the loop completes without returning, the final `current_winner` must be the largest element in the array and is the guaranteed winner. Return `current_winner`.

# Solutions
### CSharp

```csharp
public class Solution { public int GetWinner ( int [] arr , int k ) { int maxElement = arr [ 0 ], count = 0 ; for ( int i = 1 ; i < arr . Length ; i ++) { if ( maxElement < arr [ i ]) { maxElement = arr [ i ]; count = 1 ; } else { count ++; } if ( count == k ) { break ; } } return maxElement ; } }
```

### Java

```java
class Solution {
public
  int getWinner(int[] arr, int k) {
    int mx = arr[0];
    for (int i = 1, cnt = 0; i < arr.length; ++i) {
      if (mx < arr[i]) {
        mx = arr[i];
        cnt = 1;
      } else {
        ++cnt;
      }
      if (cnt == k) {
        break;
      }
    }
    return mx;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getWinner(vector<int> &arr, int k) {
    int mx = arr[0];
    for (int i = 1, cnt = 0; i < arr.size(); ++i) {
      if (mx < arr[i]) {
        mx = arr[i];
        cnt = 1;
      } else {
        ++cnt;
      }
      if (cnt == k) {
        break;
      }
    }
    return mx;
  }
};

```

### Python

```python
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int: mx = arr[0] cnt = 0 for x in arr[1:]: if mx < x: mx = x cnt = 1 else: cnt += 1 if cnt == k: break return mx

```