Tournament Winner with Time and Space Complexity — Competitive Programming

Question

Sample Input:

Sample Output:

Solution

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

  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.
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;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store