Find the Winner of an Array Game

Medium

Asked by:

16 views

Topics:

Arrays

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 <= 10⁵
1 <= arr[i] <= 10⁶
arr contains distinct integers.
1 <= k <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `arr` and what is the range of values within the array?
Can the input array `arr` be empty or contain only one element?
If a winner is never found (i.e., `k` is larger than the number of rounds needed for one element to dominate), what value should I return?
Are the values in the input array `arr` guaranteed to be distinct, or can there be duplicates?
Is the input `k` always a non-negative integer?

Brute Force Solution

Approach

The brute force method directly simulates the game. We repeatedly compare the first two numbers and the larger one wins, continuing until one number wins enough rounds.

Here's how the algorithm would work step-by-step:

Start by taking the first two numbers in the list.
Compare these two numbers; the bigger number is the current winner.
The loser goes to the end of the list.
Repeat this comparison with the current winner and the next number in the updated list.
Keep track of how many consecutive times a number has won.
If any number wins enough consecutive times, declare that number as the overall winner and stop.

Code Implementation

def find_the_winner_of_an_array_game_brute_force(numbers, consecutive_wins_needed):
    current_winner = numbers[0]
    consecutive_wins = 0

    for i in range(1, len(numbers)): 
        # Loop through the array and simulate each round of the game.
        if current_winner > numbers[i]:
            consecutive_wins += 1
        else:
            current_winner = numbers[i]
            consecutive_wins = 1

        # If the current winner achieves the required number of consecutive wins, we are done.
        if consecutive_wins == consecutive_wins_needed:
            return current_winner

    # If no winner is found after iterating, the max value wins.
    return current_winner

Big(O) Analysis

Time Complexity

O(n^2) – The described brute force method simulates the game turn by turn. In the worst-case scenario, we might iterate through the array multiple times. Each round involves comparing two elements and potentially moving one element to the end. In the worst case, a single element might need to compete against almost all other (n) elements and this needs to happen for multiple turns. This leads to an approximate O(n * n) or O(n^2) time complexity, because in the worst case scenario, the number of iterations grows quadratically with the size of the array n.

Space Complexity

O(1) – The provided brute force solution primarily uses a constant number of variables to track the current winner and the winning streak. It modifies the input list in place by moving the loser to the end. Therefore, it does not use any auxiliary data structures that scale with the input size N (the number of elements in the array). The space complexity is therefore constant.

Optimal Solution

Approach

The winner is the element that wins a certain number of consecutive rounds. Instead of simulating every round, we keep track of the current winner and the number of consecutive wins. The goal is to efficiently track the current winner and when it reaches the required win count.

Here's how the algorithm would work step-by-step:

Start by assuming the first element is the current winner.
Check who wins between the current winner and the next element.
If the next element wins, it becomes the new current winner, and its consecutive win count starts at 1.
If the current winner wins, increase its consecutive win count by 1.
If at any point the current winner's consecutive win count equals the required number, then that element is the winner, and we are done.
If we reach the end without a winner and the required number of consecutive wins is larger than the size, then the maximum element of the array wins.

Code Implementation

def find_winner_of_an_array_game(array, consecutive_wins_required):
    current_winner = array[0]
    consecutive_wins = 0

    for i in range(1, len(array)): 
        # Iterate through the array to simulate rounds of the game.
        if current_winner > array[i]:
            consecutive_wins += 1
        else:
            current_winner = array[i]
            consecutive_wins = 1

        # Check if the current winner has reached the required consecutive wins.
        if consecutive_wins == consecutive_wins_required:
            return current_winner

    # If the loop completes without a winner, the max element wins.
    if consecutive_wins_required > len(array):
        return max(array)

    return current_winner

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of size n at most once. In each iteration, it compares the current winner with the next element and updates the winner or the win count. The number of comparisons is directly proportional to the size of the array. Thus, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a few variables to keep track of the current winner and its consecutive win count. These variables, such as the current winner and the number of consecutive wins, consume a constant amount of space regardless of the input array's size, N. No auxiliary data structures, like lists or hash maps, are created to store intermediate results. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null array	Return -1 immediately as there's no array to process.
Array with only one element	Return the only element in the array as the winner, as it will always 'win'.
k is greater than or equal to array length - 1	The winner will stabilize after n-1 rounds where n is the array length, so simulate n-1 rounds.
All elements in the array are the same	The first element will always be the winner after one round.
Array is sorted in ascending order	The last element will become the winner after the first comparison.
Array is sorted in descending order	The first element will win initially, but the 'winner' and the next element have to continue competing.
Large array size with large k value	Optimize for space complexity; store winner and current streak, not the entire game history.
Integer overflow if array elements are very large	Ensure the data type used for comparison is large enough to accommodate the array elements.

Empty or null array

How to Handle:

Return -1 immediately as there's no array to process.

Array with only one element

How to Handle:

Return the only element in the array as the winner, as it will always 'win'.

k is greater than or equal to array length - 1

How to Handle:

The winner will stabilize after n-1 rounds where n is the array length, so simulate n-1 rounds.

All elements in the array are the same

How to Handle:

The first element will always be the winner after one round.

Array is sorted in ascending order

How to Handle:

The last element will become the winner after the first comparison.

Array is sorted in descending order

How to Handle:

The first element will win initially, but the 'winner' and the next element have to continue competing.

Large array size with large k value

How to Handle:

Optimize for space complexity; store winner and current streak, not the entire game history.

Integer overflow if array elements are very large

How to Handle:

Ensure the data type used for comparison is large enough to accommodate the array elements.