Find the Winner of an Array Game — Medium Problem & Solution

Problem statement

arr holds distinct integers. Repeatedly compare arr[0] with arr[1]: the larger stays at position 0 and the smaller is moved to the end of the array.

Return the first integer to win k consecutive rounds.

Example 1

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: 5 takes the front by beating 3, then beats 4 — two rounds in a row.

Example 2

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: Once the maximum reaches the front it wins every round, so it wins any `k`.

Example 3

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

Constraints

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr contains distinct integers.
• 1 <= k <= 10^9

How to solve Find the Winner of an Array Game

Sweep once, carrying the current champion and its consecutive-win count. A larger element takes over with a streak of 1; anything smaller extends the streak. If the streak reaches k, that element is the answer; otherwise the maximum has surfaced and wins every round from then on.

Approach

1. Start with cur = arr[0] and wins = 0.
2. For each later element: if it is larger, it becomes cur with wins = 1; otherwise increment wins.
3. Return cur as soon as wins == k.
4. After the sweep, return cur — by then it is the array maximum.

Why it works

The rotation never needs to be simulated because the elements pushed to the back are, in order, exactly the ones the sweep has already passed — so the first pass sees every challenger in the order it would arrive. And once the maximum is at the front nothing can dislodge it, so a k larger than the array is answered by the maximum without any extra work.

Complexity

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

Pitfalls

• k can exceed the array length, so a simulation must be bounded or avoided.
• A new champion starts its streak at 1 — it just won a round.
• The elements are distinct, so there are no ties to resolve.

Reference solution

Python

from typing import List

def getWinner(arr: List[int], k: int) -> int:
    cur, wins = arr[0], 0
    for v in arr[1:]:
        if v > cur:
            cur, wins = v, 1
        else:
            wins += 1
        if wins == k:
            return cur
    return cur

JavaScript

var getWinner = function(arr, k) {
    var cur = arr[0], wins = 0;
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] > cur) { cur = arr[i]; wins = 1; } else wins++;
        if (wins === k) return cur;
    }
    return cur;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium
• Partition Array for Maximum Sum Medium