Rank Teams By Votes - Leetcode Solution

Problem Statement

In this problem, we are given a list of team votes in which each element is a string containing the names of team members who voted for that team. Our task is to rank the teams based on the number of votes they received.

Rules for ranking:

• Teams with higher number of votes come first.
• If two or more teams have the same number of votes, then they are ranked alphabetically based on the names of team members who voted for them.

For example, if there are three teams, A, B and C, and A and B have the same number of votes, then the team with the members whose names come first alphabetically is ranked higher.

Solution

To solve this problem, we need to perform the following steps:

1. Create a dictionary with the key as the team name and the value as a list containing the number of votes and the list of names of team members who voted for that team.
2. Iterate over the given votes list and update the dictionary accordingly.
3. Sort the dictionary based on the number of votes and, in case of the same number of votes, sort based on the names of team members who voted for them.
4. Return the sorted list of team names.

Here is the Python code that implements the above approach:

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        team_votes = {}
        for vote in votes:
            for i, team in enumerate(vote):
                if team not in team_votes:
                    team_votes[team] = [0] * len(vote)
                team_votes[team][i] += 1
                
        sorted_teams = sorted(team_votes.keys(), key=lambda x: (-team_votes[x][0], x))
        
        return "".join(sorted_teams)

In the above code:

• We first create an empty dictionary team_votes.
• We then iterate over the given votes list. For each vote, we iterate over the characters in the vote and update the dictionary team_votes accordingly. We keep a list of zeros with length equal to the length of each vote, which helps to keep track of the number of votes received by each team at each position.
• After updating the dictionary, we sort it based on the number of votes received by each team. For this, we use the sorted() method with the key argument as a lambda function. The lambda function returns a tuple of the negative votes received by each team at the first position and the name of the team. We take the negative of the votes to sort it in descending order. In case of a tie, we use the team name to break the tie.
• Finally, we return the sorted list of team names as a string.

Time Complexity

The time complexity of this solution is O(NM log M), where N is the number of teams and M is the length of each vote string.

• In the worst case, we need to iterate over all the votes, which takes O(NM) time.
• Sorting each team's votes and sorting all the teams based on votes and names takes O(M log M) time for each team, which sums to O(NM log M).

Space Complexity

The space complexity of this solution is O(NM), which is used to store the team_votes dictionary.

1