Find Players With Zero or One Losses

medium array hash map sorting

Problem

You are given a list of matches, where each match is a pair [winner, loser]. Every value is a player id. Return a list with two sorted groups: first, the players who never lost a single match, and second, the players who lost exactly one match. Only include players that appear in at least one match, and return each group sorted in increasing order.

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

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

Players 1, 2, and 10 won every match they played (zero losses). Players 4, 5, 7, and 8 each lost exactly once. Player 3, 6, and 9 lost two or more times, so they are left out.

matches (pairs like 1-3, 2-3, …)

def find_winners(matches):
    losses = {}
    for winner, loser in matches:
        losses.setdefault(winner, 0)
        losses[loser] = losses.get(loser, 0) + 1
    zero = sorted(p for p, c in losses.items() if c == 0)
    one = sorted(p for p, c in losses.items() if c == 1)
    return [zero, one]

function findWinners(matches) {
  const losses = new Map();
  for (const [winner, loser] of matches) {
    if (!losses.has(winner)) losses.set(winner, 0);
    losses.set(loser, (losses.get(loser) || 0) + 1);
  }
  const zero = [], one = [];
  for (const [p, c] of losses) {
    if (c === 0) zero.push(p);
    else if (c === 1) one.push(p);
  }
  return [zero.sort((a, b) => a - b), one.sort((a, b) => a - b)];
}

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, Integer> losses = new HashMap<>();
        for (int[] m : matches) {
            losses.putIfAbsent(m[0], 0);
            losses.put(m[1], losses.getOrDefault(m[1], 0) + 1);
        }
        List<Integer> zero = new ArrayList<>(), one = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : losses.entrySet()) {
            if (e.getValue() == 0) zero.add(e.getKey());
            else if (e.getValue() == 1) one.add(e.getKey());
        }
        Collections.sort(zero);
        Collections.sort(one);
        return Arrays.asList(zero, one);
    }
}

vector<vector<int>> findWinners(vector<vector<int>>& matches) {
    map<int, int> losses;
    for (auto& m : matches) {
        if (!losses.count(m[0])) losses[m[0]] = 0;
        losses[m[1]]++;
    }
    vector<int> zero, one;
    for (auto& e : losses) {
        if (e.second == 0) zero.push_back(e.first);
        else if (e.second == 1) one.push_back(e.first);
    }
    return { zero, one };
}

Explanation

We only care about how many times each player lost. So the whole problem reduces to a counting exercise over a hash map that maps a player id to their loss count.

We scan every match once. For the winner, we make sure they exist in the map (so winners-only players still show up with a count of 0), but we do not bump their count. For the loser, we add one to their loss count.

After the scan, the map holds every player that played at least one match together with their exact number of losses. We pour the keys into two buckets: those with count 0 (never lost) and those with count 1 (lost exactly once). Players with two or more losses are simply ignored.

The problem asks for each group in increasing order, so we sort both buckets before returning [zero, one].

Trace of the example: player 3 loses to 1 and 2, so it ends with 2 losses and is dropped. Players 1, 2, and 10 never appear as a loser, so they land in the zero bucket. Players 4, 5, 7, and 8 each show up as a loser exactly once, so they land in the one bucket — giving [[1, 2, 10], [4, 5, 7, 8]].

Time: O(n + k log k) Space: O(k)