1535. Find the Winner of an Array Game

MediumArraySimulation
Leetcode Link

Problem Description

In this problem, you are given an array arr consisting of distinct integers and an additional integer k. The problem simulates a game played with the elements of the array which involves repeated comparisons between the first two elements (arr[0] and arr[1]). In each round of the game, if arr[0] is greater than arr[1], then arr[0] wins the round, remains at the first position, and the loser (arr[1]) is moved to the end of the array. Conversely, if arr[1] is greater, it takes the first position, and the previous arr[0] is moved to the end. Rounds continue until one of the integers wins k consecutive rounds. The task is to determine which integer will win the game under these rules.

It is important to note that the game will have a winner and that each integer in the array is unique.

Intuition

The intuition behind the solution is quite straightforward with a keen observation of the game's rules. Since the integers are distinct, there will be a 'strongest' integer in the array that will eventually defeat all others in comparison. As soon as this 'strongest' integer wins for the first time, it will keep winning against all the other integers. Thus, we can conclude that this 'strongest' integer only needs to win k times in a row or beat all other integers once to become the winner of the game.

Understanding this core principle, we can iterate through the array and maintain a count of consecutive wins for the current maximum integer we've found (mx). If the current maximum integer wins against the next challenger (x), we increment the win counter (cnt). If the challenger wins, it becomes the new maximum integer and the win counter resets to 1. This process continues until either the counter reaches k or we have checked all integers in the array. At that point, the current maximum (mx) is the winner of the game.

If the win counter reaches k, the loop ends early and we return the current maximum integer. This approach works because we will either find the 'strongest' integer before iterating through the entire array or confirm the maximum integer by checking each element once.

Solution Approach

The implementation of the solution leverages a simple iterative approach, which falls under the category of simulation algorithms. Simulation involves mimicking the operation of a real-world process or system over time.

The algorithm makes use of two variables, mx to keep track of the current maximum integer (the one that would potentially win the game) and cnt to count the number of consecutive rounds the current maximum integer has won. Initially, mx is set to the first element in the array (arr[0]), and cnt is set to zero as no rounds have been played yet.

The solution iterates over the elements of the array starting from the second element (arr[1]). For each element x in the array, the algorithm does the following:

  • Check if the current maximum integer mx is smaller than the current element x.
    • If so, this means x wins this round, so mx is updated to x, and cnt is reset to 1 since x has now won 1 consecutive round.
    • Otherwise, mx has won the current round against x, so we increment cnt to reflect the additional consecutive win.

After each comparison, the algorithm checks if the win counter cnt has reached k. If it has, it means the current maximum integer mx has won k consecutive rounds, and we can break out of the loop.

The loop continues until either:

  • The win counter cnt has reached k or;
  • All elements in the array have been compared with mx.

Once the loop has finished (either by reaching the end of the array or by cnt reaching k), mx holds the value of the winning integer, which is then returned.

This solution works efficiently because it leverages the fact that the largest element in the array will inevitably end up at position 0 and stay there until the game is finished. As soon as it gets to position 0, the maximum number of comparisons it will have to go through is k or the number of remaining elements in the array, whichever is smaller.

Here is the solution code enclosed within code ticks for clarity:

1class Solution:
2    def getWinner(self, arr: List[int], k: int) -> int:
3        mx = arr[0]
4        cnt = 0
5        for x in arr[1:]:
6            if mx < x:
7                mx = x
8                cnt = 1
9            else:
10                cnt += 1
11            if cnt == k:
12                break
13        return mx

Through this code, we can see the application of algorithmic thinking, making use of efficient iteration and simple conditional checks to arrive at the solution. No additional data structures are needed, as we can solve the problem in a straight pass through the array, and the code runs in linear time relative to the size of the array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's consider a small example where the array arr is [2, 1, 3, 5, 4] and the additional integer k is 2. According to the rules, we need to find out which integer will win k or 2 consecutive rounds.

Initially, we set mx = arr[0], which is 2, and cnt = 0. Then we start iterating over the array from arr[1].

  1. Compare mx (2) with arr[1] (1):
    • mx is greater than arr[1], so mx remains the same and cnt is incremented to 1.
    • The updated values are mx = 2, cnt = 1.
  2. Next, we compare mx (2) with arr[2] (3):
    • mx is smaller than arr[2], so mx becomes 3 and cnt is reset to 1.
    • The updated values are mx = 3, cnt = 1.
  3. We then compare mx (3) with arr[3] (5):
    • Again, mx is smaller, so mx becomes 5, and cnt is reset to 1.
    • The updated values are mx = 5, cnt = 1.
  4. Finally, we compare mx (5) with arr[4] (4):
    • mx is greater, so mx stays as 5, and cnt is incremented to 2.
    • The updated values are mx = 5, cnt = 2.

Since cnt has now reached k (which is 2), we stop here. The integer 5 has won 2 consecutive rounds, satisfying our condition for winning the game. Therefore, 5 will be returned as the winner of the game.

Through this example, we can observe that as soon as an integer wins against its immediate challenger, the counter is updated, and if the integer continues to win consecutively or the counter reaches k, this integer is considered the game winner. The code simulates the exact steps described above to extract the winner effectively and efficiently.

Solution Implementation

1from typing import List
2
3class Solution:
4    def getWinner(self, arr: List[int], k: int) -> int:
5        # Initialize the maximum value with the first element in the array
6        max_value = arr[0]
7        # Initialize the counter for consecutive wins
8        consecutive_wins = 0
9      
10        # Iterate over the array starting from the second element
11        for value in arr[1:]:
12            # If current value is greater than the maximum value found so far,
13            # update the maximum value and reset consecutive wins counter
14            if max_value < value:
15                max_value = value
16                consecutive_wins = 1
17            else:
18                # If current value is not greater, increment the consecutive wins counter
19                consecutive_wins += 1
20          
21            # If the consecutive wins match the k value, break out of the loop
22            if consecutive_wins == k:
23                break
24      
25        # Return the maximum value which is the winner
26        return max_value
27
1class Solution {
2
3    public int getWinner(int[] arr, int k) {
4        // Current maximum element found in the array.
5        int currentMax = arr[0];
6      
7        // Initialize the count of consecutive wins for the current maximum element.
8        int count = 0;
9      
10        // Loop through the array starting from the second element.
11        for (int i = 1; i < arr.length; ++i) {
12            // If the current maximum is less than the current element of the array,
13            // update the current maximum to this new larger value
14            // and reset the count of consecutive wins to 1.
15            if (currentMax < arr[i]) {
16                currentMax = arr[i];
17                count = 1; // Reset count for the new maximum element.
18            } else {
19                // Otherwise, increment the count of consecutive wins for the current maximum.
20                ++count;
21            }
22          
23            // If the count of consecutive wins equals k, stop the loop as we found the winner.
24            if (count == k) {
25                break;
26            }
27        }
28      
29        // Return the element that has won k times in a row or is the largest in the array.
30        return currentMax;
31    }
32}
33
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to determine the winner of the game according to the given rules
7    int getWinner(vector<int>& arr, int k) {
8        int maxElement = arr[0]; // Initialize the maximum element found so far
9        int winCount = 0; // Counter for the number of consecutive wins of 'maxElement'
10
11        // Iterate through the array
12        for (int i = 1; i < arr.size(); ++i) {
13            // Check if the current element is greater than the maxElement found so far
14            if (maxElement < arr[i]) {
15                maxElement = arr[i]; // Update maxElement to the new maximum
16                winCount = 1; // Reset win counter since we have a new maxElement
17            } else {
18                // If maxElement is still greater, increase its winCount
19                ++winCount;
20            }
21            // If the winCount reaches k, current maxElement is the winner, break the loop
22            if (winCount == k) {
23                break;
24            }
25        }
26      
27        // Return the element that has won k times in a row or is the maximum element found
28        return maxElement;
29    }
30};
31
1function getWinner(arr: number[], k: number): number {
2    // Initialize the maximum number found so far to the first element of the array
3    let maxNumber = arr[0];
4    // Initialize a counter to track the number of consecutive wins
5    let winCount = 0;
6  
7    // Loop through the array starting from the second element
8    for (const current of arr.slice(1)) {
9        // If the current number is greater than the maxNumber, update maxNumber
10        // and reset the winCount since we have a new "leader"
11        if (maxNumber < current) {
12            maxNumber = current;
13            winCount = 1;
14        } else {
15            // If the current number is not greater, increment the winCount
16            ++winCount;
17        }
18      
19        // If the winCount has reached the required number of consecutive wins, break the loop
20        if (winCount === k) {
21            break;
22        }
23    }
24  
25    // Return the number which reached the required k consecutive wins (or if none did, the maxNumber)
26    return maxNumber;
27}
28

Time and Space Complexity

The given Python code implements a function to determine the winner in a game played with an array and a number k. The winner is the first integer that wins k consecutive rounds against all the subsequent integers it faces in the list.

Time Complexity:

The time complexity of the function is O(n), where n is the length of the input list arr. This is because the code iterates through the list once, comparing each element with the current maximum (mx) until either an element has won k times consecutively or we have reached the end of the list.

The worst-case scenario occurs when k is greater than the length of the list, which would result in a complete single iteration through the list. Each comparison takes O(1) time, so going through the list is O(n).

Space Complexity:

The space complexity of the function is O(1). Only a constant amount of extra space is used, which includes variables for the current maximum (mx), the current count (cnt), and any other temporary variables used within the loop (like x). This does not scale with the input size, so it remains constant.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄