LeetCode 2225 - Find Players With Zero or One Losses

The problem gives us a list of match results. Each match is represented as a pair: This means the player winner defeated the player loser. Our goal is to return two separate lists: 1. All players who never lost any match. 2. All players who lost exactly one match.

leetcodemediumarrayhash-tablesortingcounting

LeetCode Problem 2225

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Counting

Solution

Problem Understanding

The problem gives us a list of match results. Each match is represented as a pair:

[winner, loser]

This means the player winner defeated the player loser.

Our goal is to return two separate lists:

  1. All players who never lost any match.
  2. All players who lost exactly one match.

Both lists must be sorted in increasing order.

An important detail is that we only consider players who appeared in at least one match. A player who never appeared anywhere should not be included in the answer.

The constraints are large:

  • Up to 10^5 matches
  • Player IDs can also go up to 10^5

Because of this, we need an efficient solution. Any algorithm that repeatedly scans the entire matches list for every player would become too slow.

The problem also guarantees that:

  • winner != loser
  • Every match is unique

This removes complications such as duplicate match records or self matches.

Several edge cases are important:

  • A player may only appear as a winner and never as a loser.
  • A player may lose multiple times.
  • No player may have exactly one loss.
  • A player may appear many times across matches.
  • Players are not guaranteed to appear in sorted order.

A correct solution must properly track all players and count losses accurately.

Approaches

Brute Force Approach

A brute force solution would first collect all unique players. Then, for every player, we could scan through the entire matches array and count how many times that player appears as a loser.

If the loss count is:

  • 0, add the player to the first list
  • 1, add the player to the second list

This works because we explicitly compute the exact number of losses for every player.

However, this approach is inefficient. Suppose there are n matches and p players. For each player, we scan all matches, resulting in approximately:

O(p * n)

In the worst case, both values can be around 10^5, making the solution far too slow.

Optimal Approach

The key observation is that we only care about the number of losses for each player.

Instead of repeatedly scanning matches, we can process every match exactly once and maintain a hash map:

loss_count[player] = number of losses

For every match:

[winner, loser]

we:

  • Ensure the winner exists in the map
  • Increment the loser's loss count

After processing all matches, we simply iterate through the map:

  • Players with 0 losses go into the first result list
  • Players with 1 loss go into the second result list

Finally, we sort both lists.

This is efficient because each match is processed once, and hash map operations are approximately O(1).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(p × n) O(p) Repeatedly scans all matches for every player
Optimal O(n + p log p) O(p) Counts losses in one pass, then sorts results

Where:

  • n = number of matches
  • p = number of unique players

Algorithm Walkthrough

Step 1: Create a hash map for loss counts

We use a hash map where:

key = player ID
value = number of losses

This allows constant time updates and lookups.

Step 2: Process every match once

For each match:

[winner, loser]

we perform two operations:

  1. Ensure the winner exists in the map.

If the winner has never lost before, they may not yet exist in the map. We initialize them with 0. 2. Increment the loser's loss count.

Since the loser lost this match, we increase their count by one.

Step 3: Build the result lists

After processing all matches, the hash map contains every player and their total losses.

We iterate through the map:

  • If losses == 0, append to zero_losses
  • If losses == 1, append to one_loss

Players with more than one loss are ignored.

Step 4: Sort both lists

The problem requires increasing order, so we sort both result lists before returning them.

Step 5: Return the final answer

Return:

[zero_losses, one_loss]

Why it works

The algorithm maintains the invariant that after processing every match, the hash map stores the exact number of losses for every player seen so far.

Because every match contributes exactly one loss to exactly one player, incrementing the loser's count once per match guarantees accurate totals.

Every player who appears in any match is added to the map, either as a winner or loser, ensuring no valid player is missed.

Finally, categorizing players based on their exact loss counts produces the required answer.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        loss_count = defaultdict(int)

        for winner, loser in matches:
            # Ensure winner exists in the map
            if winner not in loss_count:
                loss_count[winner] = 0

            # Increment loser loss count
            loss_count[loser] += 1

        zero_losses = []
        one_loss = []

        for player, losses in loss_count.items():
            if losses == 0:
                zero_losses.append(player)
            elif losses == 1:
                one_loss.append(player)

        zero_losses.sort()
        one_loss.sort()

        return [zero_losses, one_loss]

The implementation starts by creating a defaultdict(int) called loss_count. This automatically initializes missing entries with 0.

We iterate through every match exactly once. For each match, we first ensure the winner exists in the map. This is necessary because winners who never lose would otherwise never appear in the dictionary.

Next, we increment the loser's loss count.

Once all matches are processed, the dictionary contains the total losses for every player who participated.

We then iterate through the dictionary entries and separate players into two lists:

  • zero_losses
  • one_loss

Finally, both lists are sorted because the problem requires increasing order.

The solution is concise and efficient while directly matching the algorithm described earlier.

Go Solution

package main

import "sort"

func findWinners(matches [][]int) [][]int {
	lossCount := make(map[int]int)

	for _, match := range matches {
		winner := match[0]
		loser := match[1]

		// Ensure winner exists in the map
		if _, exists := lossCount[winner]; !exists {
			lossCount[winner] = 0
		}

		// Increment loser loss count
		lossCount[loser]++
	}

	zeroLosses := []int{}
	oneLoss := []int{}

	for player, losses := range lossCount {
		if losses == 0 {
			zeroLosses = append(zeroLosses, player)
		} else if losses == 1 {
			oneLoss = append(oneLoss, player)
		}
	}

	sort.Ints(zeroLosses)
	sort.Ints(oneLoss)

	return [][]int{zeroLosses, oneLoss}
}

The Go implementation follows the same logic as the Python version.

A map[int]int stores loss counts. Since Go maps return the zero value for missing keys, incrementing a loser's count works naturally.

One important detail is ensuring winners are explicitly inserted into the map with value 0. Otherwise, winners who never lose would not appear during the final iteration.

Slices are used to store the result lists, and the standard library sort.Ints function sorts them in increasing order.

Worked Examples

Example 1

Input:

matches = [
    [1,3],
    [2,3],
    [3,6],
    [5,6],
    [5,7],
    [4,5],
    [4,8],
    [4,9],
    [10,4],
    [10,9]
]

Processing Matches

Match Action loss_count State
[1,3] 3 loses once {1:0, 3:1}
[2,3] 3 loses again {1:0, 2:0, 3:2}
[3,6] 6 loses once {1:0, 2:0, 3:2, 6:1}
[5,6] 6 loses again {1:0, 2:0, 3:2, 5:0, 6:2}
[5,7] 7 loses once {1:0, 2:0, 3:2, 5:0, 6:2, 7:1}
[4,5] 5 loses once {1:0, 2:0, 3:2, 4:0, 5:1, 6:2, 7:1}
[4,8] 8 loses once {1:0, 2:0, 3:2, 4:0, 5:1, 6:2, 7:1, 8:1}
[4,9] 9 loses once {1:0, 2:0, 3:2, 4:0, 5:1, 6:2, 7:1, 8:1, 9:1}
[10,4] 4 loses once {1:0, 2:0, 3:2, 4:1, 5:1, 6:2, 7:1, 8:1, 9:1, 10:0}
[10,9] 9 loses again {1:0, 2:0, 3:2, 4:1, 5:1, 6:2, 7:1, 8:1, 9:2, 10:0}

Final Categorization

Players with 0 losses:

[1, 2, 10]

Players with 1 loss:

[4, 5, 7, 8]

Final answer:

[[1,2,10],[4,5,7,8]]

Example 2

Input:

matches = [
    [2,3],
    [1,3],
    [5,4],
    [6,4]
]

Processing Matches

Match Action loss_count State
[2,3] 3 loses once {2:0, 3:1}
[1,3] 3 loses again {1:0, 2:0, 3:2}
[5,4] 4 loses once {1:0, 2:0, 3:2, 5:0, 4:1}
[6,4] 4 loses again {1:0, 2:0, 3:2, 5:0, 4:2, 6:0}

Final Categorization

Players with 0 losses:

[1, 2, 5, 6]

Players with 1 loss:

[]

Final answer:

[[1,2,5,6],[]]

Complexity Analysis

Measure Complexity Explanation
Time O(n + p log p) One pass through matches, then sorting result lists
Space O(p) Hash map stores all unique players

Where:

  • n is the number of matches
  • p is the number of unique players

The counting phase is linear because each match is processed exactly once.

Sorting dominates the final step. In the worst case, almost all players could belong to one of the result lists, producing O(p log p) sorting complexity.

The space usage is linear because the hash map stores one entry per unique player.

Test Cases

from typing import List

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict

        loss_count = defaultdict(int)

        for winner, loser in matches:
            if winner not in loss_count:
                loss_count[winner] = 0

            loss_count[loser] += 1

        zero_losses = []
        one_loss = []

        for player, losses in loss_count.items():
            if losses == 0:
                zero_losses.append(player)
            elif losses == 1:
                one_loss.append(player)

        zero_losses.sort()
        one_loss.sort()

        return [zero_losses, one_loss]

sol = Solution()

# Example 1 from problem statement
assert sol.findWinners([
    [1,3],[2,3],[3,6],[5,6],[5,7],
    [4,5],[4,8],[4,9],[10,4],[10,9]
]) == [[1,2,10],[4,5,7,8]]

# Example 2 from problem statement
assert sol.findWinners([
    [2,3],[1,3],[5,4],[6,4]
]) == [[1,2,5,6],[]]

# Single match case
assert sol.findWinners([
    [1,2]
]) == [[1],[2]]

# Player loses multiple times
assert sol.findWinners([
    [1,2],
    [3,2],
    [4,2]
]) == [[1,3,4],[]]

# Multiple players with exactly one loss
assert sol.findWinners([
    [1,2],
    [2,3],
    [4,5]
]) == [[1,4],[2,3,5]]

# Players appear in unsorted order
assert sol.findWinners([
    [10,1],
    [8,2],
    [6,3]
]) == [[6,8,10],[1,2,3]]

# Chain of matches
assert sol.findWinners([
    [1,2],
    [2,3],
    [3,4],
    [4,5]
]) == [[1],[2,3,4]]

# All players lose at least twice
assert sol.findWinners([
    [1,2],
    [3,2],
    [4,5],
    [6,5]
]) == [[1,3,4,6],[]]

# Larger mixed case
assert sol.findWinners([
    [1,5],
    [2,5],
    [3,6],
    [4,6],
    [7,8]
]) == [[1,2,3,4,7],[8]]

Test Summary

Test Why
Problem example 1 Validates standard mixed scenario
Problem example 2 Validates empty one-loss list
Single match Smallest meaningful input
One player loses many times Ensures repeated losses are counted correctly
Multiple one-loss players Verifies grouping logic
Unsorted player IDs Ensures final sorting works
Chain structure Tests cascading win/loss relationships
No one-loss players Ensures empty result handling
Larger mixed case Tests multiple disconnected groups

Edge Cases

Players Who Only Win

A player may appear exclusively as a winner and never as a loser. This is important because such players would never receive a loss count increment.

A buggy implementation might accidentally omit these players entirely.

The solution handles this by explicitly inserting every winner into the hash map with loss count 0 if they are not already present.

Players With Multiple Losses

Some players may lose many matches. The algorithm must ensure these players are excluded from both result lists unless their total losses equal exactly 0 or 1.

The implementation correctly handles this because every loss increments the count exactly once, and the final filtering checks for equality with 0 or 1.

Empty One-Loss Result

It is possible that no player loses exactly once.

For example:

[[1,2],[3,2]]

Player 2 loses twice, while players 1 and 3 never lose.

The implementation naturally handles this because no player satisfies the losses == 1 condition, so the second list remains empty.

Input Order Is Arbitrary

Matches are not guaranteed to be sorted, and player IDs can appear in any order.

A naive solution that assumes insertion order is sorted would fail.

The implementation explicitly sorts both result lists before returning them, guaranteeing correct output ordering regardless of input order.