LeetCode 1366. Rank Teams by Votes

Problem Clarification

Each voter gives a full rank of teams (A~Z) from highest to lowest. Order teams by the number of position-one votes. If multiple teams tie in the first position, consider the second position to resolve the conflict; if they tie again, continue to consider the next position; if there is still a tie when all positions are considered, the tied teams are ordered alphabetically.

Input: votes = ["WXYZ", "XYZW"]
Output: "XWYZ"
Explanation: X has same votes as W for the first position, but X has more votes than W for the second position.

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: There is a tie and the teams are ranked alphabetically.

Analysis

The key is to truly understand the problem discription: all teams are ranked by the votes they got for the first position; only when ties are found, votes for following positions are considered.

One misunderstanding that reads too much into the “speciality” of the ranking system (as stated in the problem description) might be: select the first-place team by number of votes for first position (resolve conflicts accordingly), then select the second place from the rest teams by number of votes for second position (resolve conflicts accordingly), and so on. This way, the answer for the above first example would be "XYZW".

The ranking system in this problem is actually not that “special”, and has been used in most Olympics medal table: gold medal count matters the most, silver next, and bronze the least.

Solution: for each team, count its votes for each position to get its score list, then sort teams by their score lists; to resolve “ultimate” tie, append team character to the score list, or sort the team alphabetically beforehand so the sequence stays stable when sorting by the score lists (see built-in sorting in Python).

Code

Constraints offered already:

• number of voters 1~1000
• number of teams 1~26: unique characters from A~Z
• each voter give a valid full rank of teams

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        numVoters = len(votes)
        if numVoters == 1:
            return votes[0]
        
        teams = votes[0]
        numTeams = len(teams)
        if numTeams == 1:
            return votes[0]
        
        team2votes = {team: [0] * numTeams + [team] for team in teams} 
        for vote in votes:
            for idx, team in enumerate(vote):
                team2votes[team][idx] -= 1
                
        return ''.join(sorted(teams, key=team2votes.__getitem__))