Tournament Winners

hard hash map aggregation group by

Problem

Each player belongs to a group. Every match records two players from the same group with their scores. A player's points are the sum of every score they earned across all matches (whether they were the first or second player). For each group, return the player with the highest total points; ties are broken by the lowest player_id.

Inputgroups: 15→1, 25→1, 30→2, 45→2; matches: (15,45,3,0) (30,25,1,2) (30,15,0,2) (40,45,5,4)

Outputgroup 1 → 15, group 2 → 45

In group 1, player 15 scores 3+2 = 5 and player 25 scores 2, so 15 wins. In group 2, player 45 scores 0+4 = 4 versus player 30's 1+0 = 1, so 45 wins (player 40 is ignored — only listed players count).

players (id:group, comma-separated)

matches (p1 p2 s1 s2; semicolon-separated)

def tournament_winners(group_of, matches):
    score = {}
    for p1, p2, s1, s2 in matches:
        score[p1] = score.get(p1, 0) + s1
        score[p2] = score.get(p2, 0) + s2
    best = {}
    for pid, gid in sorted(group_of.items()):
        pts = score.get(pid, 0)
        if gid not in best or pts > best[gid][1]:
            best[gid] = (pid, pts)
    return {g: best[g][0] for g in best}

function tournamentWinners(groupOf, matches) {
  const score = new Map();
  for (const [p1, p2, s1, s2] of matches) {
    score.set(p1, (score.get(p1) || 0) + s1);
    score.set(p2, (score.get(p2) || 0) + s2);
  }
  const best = new Map();
  const ids = [...groupOf.keys()].sort((a, b) => a - b);
  for (const pid of ids) {
    const gid = groupOf.get(pid);
    const pts = score.get(pid) || 0;
    if (!best.has(gid) || pts > best.get(gid).pts) best.set(gid, { pid, pts });
  }
  const out = new Map();
  for (const [g, v] of best) out.set(g, v.pid);
  return out;
}

Map<Integer, Integer> tournamentWinners(Map<Integer, Integer> groupOf, int[][] matches) {
    Map<Integer, Integer> score = new HashMap<>();
    for (int[] m : matches) {
        score.merge(m[0], m[2], Integer::sum);
        score.merge(m[1], m[3], Integer::sum);
    }
    Map<Integer, Integer> bestId = new HashMap<>(), bestPts = new HashMap<>();
    List<Integer> ids = new ArrayList<>(groupOf.keySet());
    Collections.sort(ids);
    for (int pid : ids) {
        int gid = groupOf.get(pid), pts = score.getOrDefault(pid, 0);
        if (!bestId.containsKey(gid) || pts > bestPts.get(gid)) {
            bestId.put(gid, pid);
            bestPts.put(gid, pts);
        }
    }
    return bestId;
}

map<int, int> tournamentWinners(map<int, int>& groupOf, vector<array<int, 4>>& matches) {
    unordered_map<int, int> score;
    for (auto& m : matches) {
        score[m[0]] += m[2];
        score[m[1]] += m[3];
    }
    map<int, int> bestId, bestPts;
    for (auto& [pid, gid] : groupOf) {
        int pts = score.count(pid) ? score[pid] : 0;
        if (!bestId.count(gid) || pts > bestPts[gid]) {
            bestId[gid] = pid;
            bestPts[gid] = pts;
        }
    }
    return bestId;
}

Explanation

We need the top scorer in each group, where a player's score is the sum of points across every match they played. The plan is two passes: first tally everyone's points in a hash map, then pick the best player per group.

In the first loop we build score: for each match (p1, p2, s1, s2) we add s1 to player p1 and s2 to player p2. A player accumulates points whether they were listed first or second.

In the second loop we scan players in ascending id order (using sorted). For each player we look at their group and update best[gid] only if this player has strictly more points than the current leader. Scanning ids low-to-high plus the strict > means ties are naturally won by the smallest id.

Example: group 1 has players 15 and 25. Player 15 scores 3 + 2 = 5, player 25 scores 2, so 15 wins group 1. In group 2, player 45 scores 0 + 4 = 4 beating player 30's 1, so 45 wins. Output: group 1 → 15, group 2 → 45.

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