There is an algorithms tournament taking place where teams of programmers compete against each other to solve 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 as a time, for each competition, one team is designated the home team while the other 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 winning team is the team with the most points.
Given an array of pairs representing the teams that have competed against each other an an array containing the result of each competition, create a function that returns the winner of the tournament.
First, let’s initiate our function, and create a variable for the home team, set to 1.
Next we can create two more variables, one to represent the current best team, the other to represent the scores, which will contain the score for the current best team, set to 0.
Next, let’s start a for loop, initiated with an index (i) and for each competition in competition(s). We’ll use the index to create a singular result variable, and create variables to represent the home team and away team. This will look like the following:
Now, let’s use logic to set the value for the next variable that we need to create, winningTeam.
Next, in order to update the scores accordingly, let’s create a helper method that will handle this task. As the input, the helper method will take in three parameters: a team, the number of points, and the scores dictionary.
How the helper method works is, if the input team isn’t references in the (scores) dictionary, then create an entry for that team, set to 0.
Then, that team’s points will be incremented by the input value of (points).
Since the helper method is created now, we can invoke it, then proceed to taking care of the value that (currentBest) is set to.
If the (winningTeam) has more points than the (currentBest), then set the value of the (currentBest) to be (winningTeam).
Once we’re done with these conditions, finally we can return the value of (currentBest).
The final code should look like the following:
The Complexity Analysis
The time complexity of this solution is O(n) time, where (n) is the amount of competitions.
The space complexity of this solution is O(t) time, where (t) is the number of teams.