Tournament Winner with Time and Space Complexity — Competitive Programming

Question — 4 (Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve another easy problem, Tournament Winner.

We will find the Time and Space complexity of our solution and will guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Github Repository Link: Github/TournamentWinner

Go to the previous question → Question — 3 (Validate Subsequence)

Go to the next question → Question — 5 (Non-Constructible change)

Code Wrestling

Question

There’s an algorithms tournament taking place in which teams of programmers compete against each other to solve algorithmic problems as fast as possible. Teams compete in a round robin, where each team faces off against all other teams. Only two teams compete against each other at a time, and for each competition, one team is designated the home team, while the other team is the away team. In each competition there’s always one winner and one loser; there are no ties. A team receives 3 points if it wins and 0 points if it loses. The winner of the tournament is the team that receives the most amount of points.

Given an array of pairs representing the teams that have competed against each other and an array containing the results of each competition, write a function that returns the winner of the tournament.

The input arrays are named competitions and results, respectively. The competitions array has elements in the form of [homeTeam, awayTeam], where each team is a string of at most 30 characters representing the name of the team. The results array contains information about the winner of each corresponding competition in the competitions array. Specifically, results[i] denotes the winner of competitions[i], where a 1 in the results array means that the home team in the corresponding competition won and a 0 means that the away team won.

It’s guaranteed that exactly one team will win the tournament and that each team will compete against all other teams exactly once.It’s also guaranteed that the tournament will always have at least two teams.

Sample Input:

competitions = [
[“HTML”, “C#”],
[“C#”, “Python”],
[“Python”, “HTML”],
]

results = [0, 0, 1]

Sample Output:

“Python”

// C# beats HTML, Python Beats C#, and Python Beats HTML.
// HTML — 0 points
// C# — 3 points
// Python — 6 points

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

The main objective here is to find the team which scored a maximum.

Approach:

So we need to calculate the score of each team and then declare who’s the winner. So the first thing that comes to mind is to create a dictionary. And then iterate over the competitions and then calculate the scores based on the results array and store it into the dictionary, and also keep a track of max value in the dictionary. And in the end, check whoever has the highest score, is the winner.

competitions = [
[“HTML”, “C#”],
[“C#”, “Python”],
[“Python”, “HTML”],
]

results = [0, 0, 1]

1. Create a dictionary as scores, having key as string and value as an integer. And along with that create two flags one for storing maximum Value as maxValue and another one for storing the key as currentWinner, (basically the name of team).
2. Now iterate over results, so the first element is 0, which means for the first competition ([homeTeam, awayTeam]), away team wins, which means C# wins.
3. Check if key “C#” is already present in a dictionary? No, it’s not, the dictionary is empty, thus store the key as C#, and assign its value as 3 (the winner gets 3 points), and as of now the max value is 3, and currentWinner is C#.
4. Now iterate to the second result, it’s 0 again, that means for the second competition, again away team wins, that means Python wins.
5. Check if key “Python” is already present in a dictionary? No, it’s not present, thus store the key as Python and assign its value as 3, since both C# and Python are in the same position as of now, let’s keep C# as currentWinner and keep maxValue as 3.
6. Now the last element of results is 1, which means for the last competition, the home team wins, thus python wins again.
7. Check if Python is already resent in the dictionary? Yes, it is present in the dictionary, and thus the old value was 3, now add 3 more because it won again, and thus the final value is 6 and store it in the dictionary. And now the maxValue is 6, and the currentWinner is Python.
8. We don't have any more values in the results array, thus return the currentWinner value, which is Python. Hence the solution.

Let’s see the code snippet:(C#)

private string GetWinner(List<List<string>> competitions, List<int> results)
{    
     // Time Complexity - O(n)
     // Space Complexity - O(k) [k is no. of team]
     Dictionary<string, int> scores = new Dictionary<string, int>();
     int maxValue = 0;
     string maxValueKey = "";
     for (int i = 0; i < results.Count; i++)
     {
        int index = results[i] == 0 ? 1 : 0;
        string key = competitions[i][index];
        if (!scores.ContainsKey(key))
        {
            scores[key] = 3;
        }
        else
        {
            scores[key] += 3;
        }
        if (scores[key] > maxValue)
        {
            maxValueKey = key;
            maxValue = scores[key];
        }
     }
     return maxValueKey;
}

Here, the Time Complexity is O(n) because of one for loop, and Space Complexity is O(k) because we are storing the scores in a dictionary, and k is the number of teams.

Github Repository Link: Github/TournamentWinner

Go to the previous question → Question — 3 (Validate Subsequence)

Go to the next question → Question — 5 (Non-Constructible change)

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.

Code Wrestling