Problem Description

The "Tournament Winners" problem asks you to determine the overall winner of a round-robin tournament given a list of competitions and their corresponding results. Each competition is played between two teams, and the winner gets 3 points while the loser gets 0 points. At the end, you must return the name of the team with the highest total points.

• You are given two inputs:
  • competitions: a list of pairs, where each pair represents a match between two teams.
  • results: a list of integers, where each value corresponds to the result of the competition at the same index. A value of 1 means the first team in the pair won, and 0 means the second team won.
• The key constraints are:
  • Each team gets 3 points for a win, 0 for a loss.
  • There is always exactly one winner (no ties).
  • The team with the most points at the end is the tournament winner.

Thought Process

To solve this problem, the first idea might be to go through each competition, keep track of the points for each team, and finally pick the team with the most points.

At first, you might think of brute-forcing by keeping an array of all teams and their points, updating it after each match, and then scanning through all teams to find the winner. But this could be inefficient, especially if there are many teams and matches.

Instead, we can use a hash map (or dictionary) to track each team's points efficiently. As we process each competition, we update the winning team's points in the map. After all matches, we simply return the team with the highest score.

This approach is both simple and efficient, as it allows us to update and retrieve scores in constant time.

Solution Approach

Let's break down the steps for an optimized solution:

1. Initialize a hash map: Use a dictionary (or map) to store each team's total points.
2. Iterate through competitions and results:
   • For each competition, determine which team won based on the corresponding result.
   • Update the winning team's score by adding 3 points. If the team is not yet in the map, add it with an initial score of 3.
3. Track the current leader:
   • Optionally, as you update scores, keep track of the team with the most points so far. This avoids needing a separate loop to find the winner at the end.
4. Return the winner:
   • After all competitions are processed, return the team with the highest score.

We use a hash map because it allows us to quickly look up and update each team's score in constant time, regardless of how many teams there are.

Example Walkthrough

Let's walk through an example:

• competitions = [["HTML", "C#"], ["C#", "Python"], ["Python", "HTML"]]
• results = [0, 0, 1]

1. First match: "HTML" vs "C#", result is 0 → "C#" wins.
   Scores: C#: 3
2. Second match: "C#" vs "Python", result is 0 → "Python" wins.
   Scores: C#: 3, Python: 3
3. Third match: "Python" vs "HTML", result is 1 → "Python" wins.
   Scores: C#: 3, Python: 6, HTML: 0

The winner is "Python" with 6 points.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N * T), where N is the number of competitions and T is the number of unique teams (if you scan all teams after every match).
  • Space Complexity: O(T) for storing team scores.
• Optimized approach (hash map):
  • Time Complexity: O(N), since each competition is processed once and hash map operations are O(1).
  • Space Complexity: O(T), where T is the number of unique teams.

Summary

The Tournament Winners problem is best solved by using a hash map to efficiently track each team's score as you process the competitions. By updating points in constant time and keeping track of the current leader, you can determine the winner in a single pass through the data. This approach is both simple and optimal for time and space.

Code Implementation

def tournamentWinner(competitions, results):
    scores = {}
    currentBestTeam = ""
    scores[currentBestTeam] = 0

    for idx, competition in enumerate(competitions):
        homeTeam, awayTeam = competition
        result = results[idx]
        winningTeam = homeTeam if result == 1 else awayTeam

        if winningTeam not in scores:
            scores[winningTeam] = 0
        scores[winningTeam] += 3

        if scores[winningTeam] > scores[currentBestTeam]:
            currentBestTeam = winningTeam

    return currentBestTeam
      

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string tournamentWinner(vector<vector<string>> competitions, vector<int> results) {
    unordered_map<string, int> scores;
    string currentBestTeam = "";
    scores[currentBestTeam] = 0;

    for (int i = 0; i < competitions.size(); ++i) {
        string homeTeam = competitions[i][0];
        string awayTeam = competitions[i][1];
        int result = results[i];
        string winningTeam = result == 1 ? homeTeam : awayTeam;

        if (scores.find(winningTeam) == scores.end())
            scores[winningTeam] = 0;
        scores[winningTeam] += 3;

        if (scores[winningTeam] > scores[currentBestTeam])
            currentBestTeam = winningTeam;
    }
    return currentBestTeam;
}
      

import java.util.*;

public class Solution {
    public String tournamentWinner(List<List<String>> competitions, List<Integer> results) {
        Map<String, Integer> scores = new HashMap<>();
        String currentBestTeam = "";
        scores.put(currentBestTeam, 0);

        for (int i = 0; i < competitions.size(); i++) {
            List<String> competition = competitions.get(i);
            String homeTeam = competition.get(0);
            String awayTeam = competition.get(1);
            int result = results.get(i);
            String winningTeam = result == 1 ? homeTeam : awayTeam;

            scores.put(winningTeam, scores.getOrDefault(winningTeam, 0) + 3);

            if (scores.get(winningTeam) > scores.get(currentBestTeam)) {
                currentBestTeam = winningTeam;
            }
        }
        return currentBestTeam;
    }
}
      

function tournamentWinner(competitions, results) {
    const scores = {};
    let currentBestTeam = "";
    scores[currentBestTeam] = 0;

    for (let i = 0; i < competitions.length; i++) {
        const [homeTeam, awayTeam] = competitions[i];
        const result = results[i];
        const winningTeam = result === 1 ? homeTeam : awayTeam;

        if (!(winningTeam in scores)) {
            scores[winningTeam] = 0;
        }
        scores[winningTeam] += 3;

        if (scores[winningTeam] > scores[currentBestTeam]) {
            currentBestTeam = winningTeam;
        }
    }
    return currentBestTeam;
}