We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rank Teams by Votes

Difficulty: Medium

Problem Description

In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition. The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter. You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above. Return a string of all teams sorted by the ranking system.

Key Insights

  • Teams are ranked based on the number of votes received for each position.
  • Ties in ranks are resolved by considering subsequent positions until a winner is found.
  • If teams are still tied after all positions, they are ranked alphabetically.

Space and Time Complexity

Time Complexity: O(N * M log M), where N is the number of votes, and M is the number of teams. Space Complexity: O(M), where M is the number of teams.

Solution

To solve the problem, we can use a combination of counting and sorting. We will:

  1. Create a counting structure (like a dictionary) where each team has a list that records the number of votes they received for each position.
  2. For each vote in the input list, iterate over the characters (teams) and update their respective counts in the counting structure.
  3. Once we have the counts, we will sort the teams based on their votes, using a custom sorting function that prioritizes:
    • Primary sort by the number of first-place votes.
    • Secondary sort by the number of second-place votes, and so on.
    • Finally, in case of a complete tie, sort alphabetically.
  4. Concatenate the sorted teams into a single string and return it.

Code Solutions

def rank_teams(votes):
    from collections import defaultdict
    
    # Step 1: Initialize the counting structure
    team_counts = defaultdict(lambda: [0] * len(votes[0]))
    
    # Step 2: Count votes for each team
    for vote in votes:
        for position, team in enumerate(vote):
            team_counts[team][position] += 1
            
    # Step 3: Sort teams based on the custom criteria
    sorted_teams = sorted(team_counts.keys(), key=lambda team: (team_counts[team], team), reverse=True)
    
    # Step 4: Join the sorted teams into a string
    return ''.join(sorted_teams)
← Back to All Questions