Abstract / Summary

Given an array of integers, repeatedly remove the maximum and the next element until one remains and identify that number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method getWinner that determines the first element in a list arr which can achieve k consecutive victories in a head-to-head comparison game. In each round the current champion is compared with the next element; the larger value stays champion and its win count increments, while a smaller value resets the champion and starts a new win streak. The algorithm returns the value that first reaches the required streak, or the maximum element when the streak length exceeds the list size.

Key Steps

The method begins with a guard clause that handles the situation where the required streak k is at least as large as the number of participants. In that case the champion must be the overall maximum, because any element can eventually defeat all others given enough rounds.

if k >= len(arr):
    return max(arr)

When only a single win is needed (k == 1), the winner is simply the larger of the first two participants, because the first comparison decides the outcome immediately.

if k == 1:
    return max(arr[:2])

The core of the algorithm initializes two variables: high holds the current champion, starting with the first element, and wins tracks the number of consecutive victories for that champion. The initial value of wins is set to -1 to offset the first self-comparison that occurs in the loop.

high = arr[0]
wins = -1  # workaround for comparison of first element against itself

A single pass iterates over every element a in arr. If the current champion high is greater than or equal to a, the champion wins another round and wins is incremented. When wins reaches k, the champion is returned as the winner.

for a in arr:
    if high >= a:
        wins += 1
        if wins == k:
            return high

If the challenger a is larger than the champion, the champion is replaced by a and the win streak restarts at 1 because the new champion has just won the current comparison.

    else:
        wins = 1
        high = a

After the loop finishes, the variable high necessarily holds the maximum element of the list, which is returned as a fallback. This covers the scenario where the loop never encounters a streak of length k before exhausting the list.

# high == max(arr)
return high

Edge Cases Handled

The implementation explicitly addresses the case where the required streak k is larger than or equal to the length of the input list. By returning max(arr) immediately, it avoids unnecessary iteration and guarantees correctness when the champion must defeat every other element.

When k equals 1, the method bypasses the main loop and directly returns the larger of the first two elements. This handles the minimal streak requirement efficiently and also covers the situation where the list contains exactly two elements.

The initialization of wins to -1 is a subtle detail that ensures the first comparison of the initial champion against itself does not incorrectly count as a win. This prevents an off-by-one error in the win count for the very first element.

If the input list contains a single element, the guard k >= len(arr) triggers and returns that sole element as the winner, correctly handling the degenerate case without entering the loop.

Performance Optimizations

The algorithm incorporates early-exit checks for two special conditions (k >= len(arr) and k == 1). These checks prevent the main loop from executing when the answer can be determined instantly, saving time for large inputs with extreme k values.

The main computation proceeds with a single linear scan of the list, using only constant-size auxiliary variables (high and wins). This in-place approach eliminates the need for additional data structures, reducing memory overhead and improving cache locality.

By updating the champion and win count directly within the loop, the method avoids any extra passes or nested iterations. The comparison high >= a handles both equality and greater-than cases in one branch, simplifying the control flow and minimizing branching overhead.

Overall, the design balances simplicity with efficiency, delivering the result with minimal computational work and memory usage.

Imagine a line of numbered blocks waiting to play a game. The game is all about which block is the biggest and strongest. Two blocks meet at the front of the line, and the larger one wins the round. The winner stays at the front to face the next block in line, while the smaller block goes to the very back of the line to wait for another turn.

The goal of this game is to find the first block that can win enough times in a row, which is the number called k.

First, the code checks if someone needs to win so many times that it is impossible for them to lose. If k is very large, the biggest block in the whole group will definitely win enough times eventually because it is bigger than everyone else.

Next, if k is just one, the code looks at the first two blocks and picks the winner immediately.

For other targets, the program keeps track of the current champion, which starts as the first block in the line. It counts how many games that champion has won. As it looks at each block in the line, it compares them. If the champion is bigger, it adds one to the win count for that champion. If the rival block is bigger, that new block becomes the fresh champion with one win, and the previous champion loses its spot.

This keeps happening until someone reaches the magic number of wins. When a champion finally wins enough times, the game stops and that block is declared the winner.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python				TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python		C#	Go	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	FelixFan1122		Java
	fsq	C++
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
FelixFan1122	Java
fsq	C++
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality