Rank Teams by Votes

Problem Description

Ah, the age-old dilemma of ranking teams based on votes! Imagine you’re at a school sports day, and everyone is trying to vote for their favorite team. But instead of a simple “I like this team” approach, you have to consider the order of preference. It’s like trying to decide which pizza topping is the best when everyone has their own unique taste.

In this problem, you are given a list of votes, where each vote is a string representing the ranking of teams (from ‘A’ to ‘Z’). Your task is to rank these teams based on the votes they receive. The catch? If two teams have the same score, the team with the higher alphabetical order wins. Because, you know, life isn’t fair, and neither is voting!

Code Solution


from dataclasses import dataclass

@dataclass
class Team:
    name: str
    rank: list[int]

    def __init__(self, name: str, teamSize: int):
        self.name = name
        self.rank = [0] * teamSize


class Solution:
    def rankTeams(self, votes: list[str]) -> str:
        teamSize = len(votes[0])
        teams = [Team(chr(ord('A') + i), teamSize) for i in range(26)]

        for vote in votes:
            for i in range(teamSize):
                teams[ord(vote[i]) - ord('A')].rank[i] += 1

        teams.sort(key=lambda x: (x.rank, -ord(x.name)), reverse=True)
        return ''.join(team.name for team in teams[:teamSize])

Approach

The approach taken in the code is straightforward yet effective. First, we create a Team class to hold the name and ranking of each team. We then initialize a list of teams (up to 26, for each letter of the alphabet). For each vote, we update the rank of the corresponding team based on its position in the vote string. Finally, we sort the teams based on their ranks and return the top teams as a string.

Time and Space Complexity

Time Complexity: O(N * M + K log K), where N is the number of votes, M is the length of each vote (team size), and K is the number of teams (up to 26). The sorting step dominates the complexity.

Space Complexity: O(K), where K is the number of teams, as we store the ranks in a list.

Real-World Example

Think of a talent show where judges give their scores for each performance. Each judge ranks the performances, and at the end, you want to determine which act was the best. Just like in our problem, if two acts receive the same score, the one that was ranked higher by the judges gets the crown.