Abstract / Summary

Find players who have lost zero or only one game from a list of match results.

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 72% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Hash Table
• Sorting

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 implementation solves the problem of classifying players based on the number of matches they have lost. It returns two groups: players who have never lost a match and players who have lost exactly one match. The algorithm processes the input list of match results, builds a set of all participants, records loss frequencies, sorts the participants, and finally extracts the two required groups.

Step 1 - Initialise data structures

The solution creates a set to hold every distinct player identifier and a dictionary that defaults missing keys to zero, which will be used to count losses.

players = set()
lost = defaultdict(int)

The set guarantees uniqueness of player IDs while the defaultdict simplifies incrementing loss counters without explicit existence checks.

Step 2 - Populate loss counts and player set

The core loop iterates over each match record, where m[0] is the winner and m[1] is the loser. For every match the loser’s counter is increased, and both winner and loser are added to the global player set.

for m in matches:
    lost[m[1]] += 1
    players.add(m[0])
    players.add(m[1])

This step ensures that every participant appears in the final result, even if they never lost a match.

Step 3 - Sort the complete player list

After gathering all identifiers, the set is converted to a list and sorted in ascending order. Sorting provides deterministic ordering for the output, which matches the problem’s requirement for ordered results.

p = sorted(players)

Step 4 - Extract players with zero and one loss

Two list comprehensions filter the sorted player list based on the loss count stored in the dictionary. The first comprehension selects identifiers whose loss count is exactly zero, forming the “perfect” group. The second selects identifiers with a loss count of one.

perfect = [i for i in p if lost[i] == 0]
one = [i for i in p if lost[i] == 1]

Because the dictionary returns zero for any player not present as a loser (thanks to defaultdict), players who never lost are correctly identified without additional checks.

Step 5 - Return the grouped result

The method returns a list containing the two previously built lists, preserving the required order: first the zero-loss group, then the one-loss group.

return [perfect, one]

Edge Cases Handled

When the input contains matches where a player appears only as a winner, the defaultdict supplies a zero loss count, allowing that player to be placed in the zero-loss group. If a player loses multiple times, the loss counter accurately reflects the total, and the player is excluded from both output groups because only zero or one loss qualifies. An empty matches list results in an empty player set; the subsequent sorting yields an empty list, and both output groups are empty, which aligns with the expected behavior for no data.

The algorithm also gracefully handles duplicate match entries. Each occurrence increments the loss counter for the loser, so a player who loses the same opponent multiple times will be counted correctly. Winners that appear multiple times are added repeatedly to the set, but the set’s uniqueness property prevents duplication in the final sorted list.

Performance Optimizations Observed

The use of a set for player collection eliminates the need for explicit duplicate checks, providing O(1) average-time insertion and membership operations. The defaultdict removes conditional branches that would otherwise be required to initialise loss counters, streamlining the inner loop. Converting the set to a sorted list is performed once after all data has been gathered, avoiding repeated sorting operations. List comprehensions for filtering are executed in a single pass over the sorted list, leveraging Python’s internal optimisations for fast iteration and element selection. Overall, the design minimises the number of passes over the data and relies on built-in data structures that are highly tuned for the operations performed.

Imagine a big group of friends who love playing tag together. Every time two kids play a game, one person wins and the other person loses. We want to sort these friends into two special teams based on how many times they have lost.

First, we look at a long list of all the games that happened. Whenever someone plays, their name goes into a big organizer bucket so we know they were part of the fun. We also keep a little tally pad for everyone who loses a game. Every time a child loses, we put a mark next to their name on the pad. If someone plays but never loses, they get no marks at all.

Once all the games are finished and the tally pad is full, it is time to organize everyone. We put all the names in an order starting from the smallest number to the largest number. This makes it much easier to find who belongs where.

To build our first team, we look at the list of all the friends and pick out everyone who has zero marks on the tally pad. These are the champs who never lost a single time.

For the second team, we look through the list again and find all the friends who have exactly one mark on the tally pad. These are the friends who played really well but had just one small slip during the day. This helps us see exactly how everyone did in the games without getting confused by all the results.

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

Time: loglinear
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	Python	Java	C++						TS
	WalkCCC	Python	Java	C++
	leetcode.ca	Python	Java	C++	JS				Go	TS
	Progiez	Python	Java	C++
github	black-shadows			C++
	chandansgowda	Python
	charles-wangkai		Java
	everthis				JS
	fartem						Ruby
	fsq			C++
	JoshCrozier				JS
	lkwq007	Python
	pruthvikp	Python
	shreymehul					C#
	suxrobGM					C#
	varunu28		Java
	vthwang		Java
	yuanliu666							Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
pruthvikp	Python
shreymehul	C#
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin

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