0722MediumArraySimulation

Ladder Winner On The Practice Lane

Tracked in this browser only

Trains the technique from

LeetCode 1535Find the Winner of an Array Game

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A club runs a ladder on its practice lane. ratings lists the players waiting in one queue from front to back, so ratings[0] is at the very front, and every rating in the list is different.

A round is played like this: the two players at the front of the queue face each other, the one with the higher rating stays where it is at the front, and the other walks to the very back of the queue. Rounds are played one after another until some player has won k rounds in a row, counting only rounds played since that player last arrived at the front. That player takes the ladder.

Return the rating of the player who takes the ladder.

Examples

Example 1

Input: ratings = [1, 4, 2, 9], k = 2
Output: 4

Round one is 1 against 4, so 4 stays at the front and 1 goes to the back, leaving the queue 4, 2, 9, 1. Round two is 4 against 2, so 4 wins again. That is two rounds in a row for 4, which is what `k` asks for.

Example 2

Input: ratings = [3, 1, 2, 9, 8], k = 7
Output: 9

3 beats 1 and 2, then loses to 9 in the third round. From that round on 9 stands at the front and wins every round that follows, so its streak passes seven.

Example 3

Input: ratings = [2, 1], k = 1
Output: 2

The queue holds only two players. 2 beats 1 in the first round, and one win in a row is all `k` asks for.

Constraints

2 <= ratings.length <= 10^5
1 <= ratings[i] <= 10^6
1 <= k <= 10^9
All ratings are different.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def ladder_winner(ratings: list[int], k: int) -> int:

Java

public int ladderWinner(int[] ratings, int k)

The intended approach

Time O(n) for n players: a single walk along the queue.Space O(1)

Whoever is standing at the front after a round is the largest rating among the players seen so far, so the queue never has to be rotated: walk the list once holding the current front player and the length of its current streak. A new player larger than the holder takes over with a streak of one, otherwise the holder's streak grows by one. Report the holder as soon as its streak hits `k`; if the walk finishes first the holder is the largest rating of all, and from then on it wins every round, so it is the answer whatever `k` is.

Pythonentry point: ladder_winner

def ladder_winner(ratings, k):
    # The player at the front is always the largest rating met so far, so one walk
    # along the queue replays every round: each new player either takes the front
    # or adds one to the current holder's streak.  If nobody reaches k during the
    # walk, the holder at the end is the largest rating in the queue, and it never
    # loses a round after that.
    # Time O(n).  Space O(1).
    holder = ratings[0]
    streak = 0
    for i in range(1, len(ratings)):
        if ratings[i] > holder:
            holder = ratings[i]
            streak = 1
        else:
            streak += 1
        if streak == k:
            return holder
    return holder

The obvious version

Play the rounds for real on a double-ended queue, popping the front two, pushing the winner back to the front and the loser to the back, and tracking the current streak. A streak of `n` rounds already forces the winner to have beaten every other player, so the target is capped at `n` to keep a huge `k` from running forever.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_ladder_winner(ratings, k):
    from collections import deque
    n = len(ratings)
    # A streak of n rounds means beating every other player, which only the largest
    # rating can do, so asking for more than n in a row picks the same player.
    need = k if k < n else n
    queue = deque(ratings)
    holder = None
    streak = 0
    while True:
        first = queue.popleft()
        second = queue.popleft()
        if first > second:
            winner, loser = first, second
        else:
            winner, loser = second, first
        if winner == holder:
            streak += 1
        else:
            holder = winner
            streak = 1
        queue.appendleft(winner)
        queue.append(loser)
        if streak >= need:
            return holder

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in