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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Solution

Method 1 - Simulation

To solve this problem, we need to simulate the game rounds, track the current winning streak, and check if any integer wins k consecutive rounds.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public int getWinner(int[] arr, int k) {
        int n = arr.length;
        int currentWinner = arr[0];
        int winCount = 0;

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

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

        return currentWinner;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def get_winner(arr, k):
    n = len(arr)
    current_winner = arr[0]
    win_count = 0

    for i in range(1, n):
        if arr[i] > current_winner:
            current_winner = arr[i]
            win_count = 1
        else:
            win_count += 1

        if win_count == k:
            return current_winner

    return current_winner

Complexity

  • Time: O(n)
  • Space: O(1)

Method 2 - Deque

We can use a Deque (double-ended queue) for more efficient operations. Here is the improved code:

Here is the approach:

  1. Initialization:
    • Initialize a deque with all elements of the array and set currentWinner to the first element.
    • Store the original value of k in originalK and calculate the maximum element maxElement in the array.
  2. Edge Case:
    • If k is greater than or equal to the array size, the maximum element will naturally win. Therefore, return maxElement.
  3. Game Loop:
    • Continue the game while the number of consecutive wins by currentWinner is less than k.
    • In each iteration, dequeue the next element.
    • Compare currentWinner with the next element:
      • If currentWinner is greater, increment the consecutiveWins counter and enqueue the next element to the end of the deque.
      • If the next element is greater, reset the consecutiveWins to 1, enqueue currentWinner, and update currentWinner to the next element.
  4. Return Result:
    • Once an element wins k consecutive rounds, return currentWinner as the winner.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {
    public int getWinner(int[] arr, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i : arr) {
            deque.offer(i);
        }

        int currentWinner = deque.poll();
        int originalK = k;
        int maxElement = Arrays.stream(arr).max().getAsInt();

        // If k is greater than or equal to the array size, the maximum element
        // will naturally win
        if (k >= arr.length) {
            return maxElement;
        }

        int consecutiveWins = 0;
        while (consecutiveWins < k) {
            int next = deque.poll();
            if (currentWinner > next) {
                consecutiveWins++;
                deque.offer(next);
            } else {
                consecutiveWins = 1;
                deque.offer(currentWinner);
                currentWinner = next;
            }
        }

        return currentWinner;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def get_winner(arr, k):
    dq = deque(arr)
    current_winner = dq.popleft()
    original_k = k
    max_element = max(arr)

    # If k is greater than or equal to the array size, the maximum element will naturally win
    if k >= len(arr):
        return max_element

    consecutive_wins = 0
    while consecutive_wins < k:
        next_element = dq.popleft()

        if current_winner > next_element:
            consecutive_wins += 1
            dq.append(next_element)
        else:
            consecutive_wins = 1
            dq.append(current_winner)
            current_winner = next_element

    return current_winner

Complexity

  • Time: O(n + m), where n is the length of the array and m is the number of operations required to find the winner. In the worst case, it can be O(n * k).
  • Space: O(n), due to the space required to store the elements in the deque.

Method 3 - Two Pointer and Hashtable

Here is the approach:

  • Initialization:
    • Initialize a dictionary wins to keep track of the number of wins for each integer.
    • Initialize two pointers i and j to traverse the array starting from positions 0 and 1, respectively.
  • Game Loop:
    • Continue the loop as long as both i and j are within the bounds of the array.
    • Compare arr[i] and arr[j]:
      • If arr[i] is greater, increment the win count for arr[i] in the wins dictionary and move to the next element by incrementing j.
      • If arr[j] is greater, increment the win count for arr[j], set i to j, and move to the next element by incrementing j.
    • If the win count for arr[i] equals k, return arr[i] as the winner.
  • Edge Case:
    • If no integer wins k consecutive rounds within the loop, find and return the maximum integer in the array as the winner.
  • Return the Winner:
    • The element with k consecutive wins is returned as the winner.
    • If no such element is found within the loop, return the maximum element in the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public int getWinner(int[] arr, int k) {
        int n = arr.length;
        HashMap<Integer, Integer> wins = new HashMap<>();
        int i = 0, j = 1;

        while (i < n && j < n) {
            if (arr[i] > arr[j]) {
                wins.put(arr[i], wins.getOrDefault(arr[i], 0) + 1);
            } else {
                wins.put(arr[j], wins.getOrDefault(arr[j], 0) + 1);
                i = j;
            }

            if (wins.get(arr[i]) == k) {
                return arr[i];
            }
            j++;
        }

        return Arrays.stream(arr).max().getAsInt();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def get_winner(arr, k):
    from collections import defaultdict

    n = len(arr)
    wins = defaultdict(int)
    i = 0
    j = 1

    while i < n and j < n:
        if arr[i] > arr[j]:
            wins[arr[i]] += 1
        else:
            wins[arr[j]] += 1
            i = j
        if wins[arr[i]] == k:
            return arr[i]
        j += 1

    return max(arr)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, because each element is processed at most twice.
  • 🧺 Space complexity: O(n), due to the dictionary used to store the number of wins for each integer.