1535. Find the Winner of an Array Game

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<sup>5</sup>

• 1 <= arr[i] <= 10<sup>6</sup>

• arr contains distinct integers.

• 1 <= k <= 10<sup>9</sup>

---

Initial Approach

As per the question we have to find the winner where k will be the total victories and victories will be decided based on the condition

when the first index array value is greater than the second one so if this case statisfies then we move the 2nd indexed array to the last shift all the remaining towards the 2nd index

And we use hashmap to store the key value where the key is the index value and the value of hashmap will be the count of how many time we win

But the bad part about this approach is that the time complexity and space complexity is complete shit

so we get runtime error in leetcode

    def getWinner(self, arr: List[int], k: int) -> int:
            win={}
            cnt=0
            if(len(arr)<2):
                return 

            while cnt<=k:
                if (win.get(arr[0])==k):
                    return arr[0]
                if(arr[0]>arr[1]):
                    temp=arr[1]
                    win[arr[0]]=win.get(arr[0],0)+1
                    cnt=max(cnt,win.get(arr[0]))
                    arr.remove(temp)
                    arr.append(temp)

                elif((arr[0]<arr[1])):
                    temp=arr[0]
                    win[arr[1]]=win.get(arr[1],0)+1
                    cnt=max(cnt,win.get(arr[1]))
                    arr.remove(temp)
                    arr.append(temp)

---

Better Approach

if you've understood the question then i dont need to explain the below code

def winner(arr,k):
    if k == 1:
        return max(arr[0], arr[1])
    if k >= len(arr):
        return max(arr)

    current_winner = arr[0]
    consecutive_wins = 0

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

        if consecutive_wins == k:
            return current_winner

    return current_winner