Problem Breakdown
We are given a list of strings votes, where each string represents one voter’s complete preference order for a set of unique team identifiers (e.g., “ABC” means Team A is preferred over B and C). Our goal is to aggregate these preferences into a single ranking string.
The sorting criteria follow a strict hierarchy:
- Primary Key: Number of votes received at Rank 0 (First place) in descending order.
- Secondary Keys: If tied on the previous rank, we look at vote counts for that specific position index moving rightward (Rank 1, then Rank 2…). We want higher counts to win here as well.
- Tie-Breaker: If a team is still indistinguishable after checking all positions, they are sorted alphabetically in ascending order (‘A’ before ‘B’).
Implicit Constraints & Edge Cases:
- Input Size:
voteslength up to 1000; each vote string length (number of teams) up to 26. This suggests an solution is acceptable, where is small constant (max 26). - Consistency: All votes contain the exact same set of characters. We don’t need to handle missing teams from specific voters because constraints guarantee consistency across all
votes. - Single Team/Voter: If there’s only one team or one voter, that team is automatically first. The logic should naturally handle this without special casing if implemented correctly (e.g., a single element list sorts itself).
Intuition
A brute force approach might try to simulate the voting process by repeatedly scanning all votes for every pair of teams to determine their relative order. This would be or worse, which is inefficient given we have up to 1000 voters.
Instead, we can pre-calculate a “scorecard” for each team. For Team ‘A’, how many votes did they get at position 0? Position 1? etc.? We store this in an array where counts[team][rank] holds the vote count.
Once we have these counts, sorting becomes trivial if our sort key reflects the problem’s rules exactly:
- Higher vote count is better In Python (ascending sort), we can negate the counts so that a higher actual count results in a smaller negative number appearing earlier? No, wait. If A has 5 votes and B has 3 votes at rank 0, we want A before B.
- Option 1: Use
reverse=Truewith positive counts. - Option 2 (Cleaner): Store
-count. Then -5 < -3. Python sorts ascending by default. So the tuple for A is smaller than B’s tuple at index 0, placing A first. This handles descending order logic naturally within standard sort withoutreverse=Trueflags which can get messy with multi-level keys.
- Option 1: Use
- Alphabetical tie-breaker: If counts are identical (tuples match), we append the team character itself to the key. Since ‘A’ < ‘B’, Python’s default string comparison will place A before B, satisfying the requirement.
Approach
- Identify Teams: Extract all unique teams from
votes[0]. The constraints guarantee every vote contains this same set of characters. - Initialize Scorecard: Create a dictionary mapping each team to an array (or list) initialized with zeros, sized by the number of ranks (
len(votes[0])). - Aggregate Votes: Iterate through
votes. For each character at indexjin stringi, increment the vote count for that character’s scorecard at positionj. This effectively counts how many times a team was ranked -th place across all voters. - Sort Teams: Sort the list of unique teams using a custom key function. The key returns a tuple:
( -votes_at_rank_0, -votes_at_rank_1, ..., team_char ).- Negative counts ensure higher vote totals sort earlier (ascending).
- Team char ensures alphabetical order for final ties.
- Construct Result: Join the sorted list of characters into a string and return it.
Complexity Analysis
- Time Complexity: , where is number of voters (length of
votes), is max teams per vote (max 26), and is the number of unique teams ().- Aggregating votes takes .
- Sorting takes , but since we construct a tuple key for each team which has length , it’s technically . Given and are small constants (max 26), this is effectively linear with respect to the input size.
- Space Complexity: to store the vote counts matrix, plus for storing unique teams during sorting. Since max characters is 26, space usage is constant relative to typical inputs ( in terms of scaling beyond small alphabet).
Solution
from typing import List
def rankTeams(votes: List[str]) -> str:
if not votes or len(votes[0]) == 1:
# If only one team exists, return it directly.
# Constraints say chars are unique per vote and consistent across voters.
return "".join(set([votes[0][0]]))
m = len(votes[0]) # Number of teams (ranks)
# Identify all participating teams from the first vote string
# Constraint guarantees consistency: votes[j] contains same chars as votes[0]
unique_teams = list(set(votes[0]))
# Initialize a dictionary to store counts for each team at each rank position.
# Key is team char, Value is a list of size m where index i holds count at rank i.
vote_counts = {team: [0] * m for team in unique_teams}
# Populate the vote counts matrix
for v in votes:
for rank_idx, team_char in enumerate(v):
vote_counts[team_char][rank_idx] += 1
def sort_key(team):
"""
Returns a tuple used by Python's default ascending sort.
Logic:
1. We want higher counts to come first (descending). Storing -count achieves this in ascending sort.
Example: Team A has 5 votes at rank 0 -> key starts with -5.
Team B has 3 votes at rank 0 -> key starts with -3.
Since -5 < -3, A comes before B. Correct.
2. We want alphabetical order for ties (ascending). Storing team_char directly works because 'A' < 'B'.
If all counts match up to the last element, this breaks the tie correctly.
"""
c_list = vote_counts[team]
# Construct tuple: (-count_rank_0, -count_rank_1, ..., count_rank_m-1) + (team_char,)
return tuple(-c for c in c_list) + (team,)
unique_teams.sort(key=sort_key)
return "".join(unique_teams)