Code Implementation

class Solution:
    def findWinners(self, matches):
        from collections import defaultdict

        loss_count = defaultdict(int)
        players = set()

        for winner, loser in matches:
            players.add(winner)
            players.add(loser)
            loss_count[loser] += 1

        zero_losses = []
        one_loss = []

        for player in players:
            if loss_count[player] == 0:
                zero_losses.append(player)
            elif loss_count[player] == 1:
                one_loss.append(player)

        return [sorted(zero_losses), sorted(one_loss)]
      

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        unordered_map<int, int> loss_count;
        unordered_set<int> players;

        for (auto& match : matches) {
            int winner = match[0], loser = match[1];
            players.insert(winner);
            players.insert(loser);
            loss_count[loser]++;
        }

        vector<int> zero_losses, one_loss;
        for (int player : players) {
            if (loss_count[player] == 0)
                zero_losses.push_back(player);
            else if (loss_count[player] == 1)
                one_loss.push_back(player);
        }

        sort(zero_losses.begin(), zero_losses.end());
        sort(one_loss.begin(), one_loss.end());
        return {zero_losses, one_loss};
    }
};
      

import java.util.*;

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> lossCount = new HashMap<>();
        Set<Integer> players = new HashSet<>();

        for (int[] match : matches) {
            int winner = match[0], loser = match[1];
            players.add(winner);
            players.add(loser);
            lossCount.put(loser, lossCount.getOrDefault(loser, 0) + 1);
        }

        List<Integer> zeroLosses = new ArrayList<>();
        List<Integer> oneLoss = new ArrayList<>();

        for (int player : players) {
            int losses = lossCount.getOrDefault(player, 0);
            if (losses == 0) {
                zeroLosses.add(player);
            } else if (losses == 1) {
                oneLoss.add(player);
            }
        }

        Collections.sort(zeroLosses);
        Collections.sort(oneLoss);
        List<List<Integer>> result = new ArrayList<>();
        result.add(zeroLosses);
        result.add(oneLoss);
        return result;
    }
}
      

var findWinners = function(matches) {
    const lossCount = new Map();
    const players = new Set();

    for (const [winner, loser] of matches) {
        players.add(winner);
        players.add(loser);
        lossCount.set(loser, (lossCount.get(loser) || 0) + 1);
    }

    const zeroLosses = [];
    const oneLoss = [];

    for (const player of players) {
        const losses = lossCount.get(player) || 0;
        if (losses === 0) zeroLosses.push(player);
        else if (losses === 1) oneLoss.push(player);
    }

    zeroLosses.sort((a, b) => a - b);
    oneLoss.sort((a, b) => a - b);

    return [zeroLosses, oneLoss];
};
      

Problem Description

Given a list called matches, where each element is a pair [winner, loser] representing the result of a match between two players, your task is to find:

• All players who have never lost any match (zero losses).
• All players who have lost exactly one match (one loss).

Return a list containing two lists:

• The first is the list of players with zero losses, sorted in increasing order.
• The second is the list of players with exactly one loss, also sorted in increasing order.

Thought Process

To solve this problem, we need to efficiently track how many times each player has lost. The naive approach would be to check every player against every match, but that would be slow and repetitive. Instead, we can use a data structure to count losses for each player as we process the matches.

The key insight is that the number of losses for each player is all we care about. Once we know each player's loss count, we can easily group them into the two required categories. This suggests using a hash map (dictionary) to map each player to their loss count, which allows us to update and access counts quickly.

We also need to make sure we include players who have never lost, even if they only appear as winners. So, we need to collect the set of all players seen in any match.

Solution Approach

• Step 1: Initialize Data Structures
  • Use a hash map (dictionary) to keep track of the number of losses for each player.
  • Use a set to keep track of all unique players who have played at least once (either as winner or loser).
• Step 2: Process Each Match
  • For each match [winner, loser] in matches:
  • Add both winner and loser to the set of players.
  • Increment the loss count of loser by 1 in the hash map.
• Step 3: Categorize Players
  • Iterate through all players in the set.
  • If a player's loss count is 0 (not present in the hash map or value is 0), add them to the zero-loss list.
  • If a player's loss count is 1, add them to the one-loss list.
• Step 4: Sort and Return
  • Sort both the zero-loss and one-loss lists in increasing order.
  • Return a list containing both lists.

This approach is efficient because:

• Hash map lookups and updates are O(1) on average.
• We only iterate through the matches and players a constant number of times.

Example Walkthrough

Let's walk through an example:

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

• After processing all matches:
  • Players seen: {1,2,3,4,5}
  • Loss counts: {2:2, 3:1, 5:1}
• Now, check each player:
  • Player 1: not in loss counts → 0 losses
  • Player 2: 2 losses
  • Player 3: 1 loss
  • Player 4: not in loss counts → 0 losses
  • Player 5: 1 loss
• Zero-loss players: [1, 4]
• One-loss players: [3, 5]
• After sorting, the result is [[1, 4], [3, 5]]

Time and Space Complexity

• Brute-force Approach:
  • For each player, count their losses by scanning all matches: O(N * P), where N = number of matches, P = number of players.
  • This is inefficient for large inputs.
• Optimized Approach (Hash Map):
  • Processing all matches: O(N)
  • Building the set of players: O(N)
  • Iterating through players to categorize: O(P)
  • Sorting the two result lists: O(P log P)
  • Overall Time Complexity: O(N + P log P)
  • Space Complexity: O(P) for the hash map and sets/lists.

Summary

The solution efficiently tracks each player's loss count using a hash map while collecting all players in a set. After processing all matches, we simply categorize players by their loss counts and sort the results. This approach is both simple and efficient, making good use of hash maps for constant-time updates and lookups. The main insight is that only the loss count per player matters, allowing us to avoid unnecessary repeated scanning of the matches.