1366. Rank Teams by Votes
Problem Description
In this problem, we have a voting system for ranking teams based on preferences from different voters. Each voter ranks all teams from their most preferred (highest rank) to least preferred (lowest rank). We need to compile the votes in a way that reflects the overall ranking of teams.
The ranking of the teams is determined by the following criteria:
- Primary Criterion: A team is ranked higher if it has received more first-place votes compared to other teams.
- Tiebreaker: If teams tie for first-place votes, then second-place votes are compared, and so forth, until the tie is broken.
- Alphabetical Order: If a tie cannot be broken with all provided ranks, teams are then ranked alphabetically.
We are given an array of strings votes
, where each string contains a voter's ranking of all the teams. The task is to return a string with all teams sorted based on the above ranking system.
Intuition
To solve this problem, we have to interpret the voting data and apply the ranking criteria to establish the correct order of all teams.
Here's the approach to derive the solution:
-
Counting the Votes: We need to keep track of how many times each team gets each rank from all voters. Therefore, for each team, we create an array of counters for each rank position. For instance, if there are
n
teams, each team will have an array of sizen
to hold the counts of being voted for each rank from 1 ton
. -
Sorting the Teams: Once we have the counts for each team per rank, we have to sort the teams. The sorting decision is based on:
- The count arrays: A team is considered higher-ranking if its count array represents more first-place votes, followed by more second-place votes if there is a tie, and so forth.
- Alphabetical order as a tiebreaker: When count arrays are identical for two teams (indicating a tie across all ranks), the team that comes first in alphabetical order is ranked higher.
-
Constructing the Final String: After sorting, we simply concatenate the teams in the order determined by sorting, which gives us the final ranking as a string.
The Python code provided uses a defaultdict
to create the count arrays for each team. It then sorts the team based on their count arrays (with first-place votes having the highest importance), and uses the negative ASCII value of the team character as a secondary sort key to handle alphabetical ties (since reverse=True
flips the usual ordering). Finally, it joins the sorted teams to form the output string reflecting the overall ranking.
Learn more about Sorting patterns.
Solution Approach
In the provided Python solution, we implement an efficient approach to rank the teams according to the voting criteria. Here's a step-by-step explanation of the implementation using algorithms, data structures, and patterns:
-
Data Structure - Default Dictionary with Arrays: We use Python's
defaultdict
with a lambda function to initialize an array of zeros for each team. This data structure is key to tracking the rank counts for each team. The lambda functionlambda: [0] * n
ensures that any new key (representing a team) in the dictionary automatically starts with an array of zeros, wheren
is the number of teams. -
Vote Counting - Enumerate Pattern: Using the
enumerate
function, we iterate over each vote and its index within the vote string. The index represents the rank given by a voter, and by incrementingcnt[c][i]
wherec
is the team, we accumulate the rank votes for every team. -
Sorting Algorithm: We then sort the teams using the sorted function with a custom sorting key. The sorting key is a tuple consisting of the count array
cnt[x]
and the negative ASCII value-ord(x)
, wherex
represents a team. Python sorts tuples based on a lexicographical order, meaning it compares the first item, then the second if needed, and so forth. The first element of the tuple ensures that teams are sorted based on the entire ranking information, while-ord(x)
is used as a tiebreaker becausesorted
is a stable sort, meaning that if two elements have the exact same count array, they will be ordered based on their ASCII character value. -
Custom Key Function for Sorting: By using the
key=lambda x: (cnt[x], -ord(x))
, we tell the sorted function to prioritize the count arrays first. Since we want the teams with the most first-place votes to be at the front, we usereverse=True
to sort the list in descending order. The negative ASCII value sorts alphabetically in the reverse (because 'A' has a smaller ASCII value than 'Z'), but reversing the list corrects this and yields the correct order. -
Building the Final String: Finally, we join the sorted list of teams into a string, which represents the teams sorted according to the rank system.
Overall, the algorithms and data structures used in the solution are chosen to efficiently handle the rank aggregation and sorting criteria as specified in the problem, resulting in a concise and performant implementation.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose there are three teams: A, B, and C, and we have the following votes from four voters:
1votes = ["BCA", "CAB", "CBA", "ABC"]
In this example, each letter represents a team, and the order of the letters in each vote string represents the ranking from the most preferred team to the least preferred team by a voter. Here, we will walk through the algorithm to determine the final ranking.
- Initialize the Default Dictionary with Arrays:
We create a default dictionary called
cnt
that will map each team to an array of zeros. Since there are three teams, each array will have a length of three.
1cnt = defaultdict(lambda: [0, 0, 0])
After observing all votes the cnt
dictionary would be (not in order):
1cnt = { 2 'A': [1, 1, 2], 3 'B': [0, 2, 2], 4 'C': [3, 1, 0] 5}
'A' has been voted first once, second once, and third twice; 'B' has been voted second and third twice, but never first; 'C' has been voted first three times, second once.
- Counting Votes:
We iterate over each vote in
votes
and each team within the vote string:
1for vote in votes: 2 for i, c in enumerate(vote): 3 cnt[c][i] += 1
Using enumeration, we increment the count of rank i for each team c.
- Sorting Teams: We now sort the teams based on their count arrays, and in case of a tie, by their alphabetical order:
1teams = sorted(cnt, key=lambda x: (cnt[x], -ord(x)), reverse=True)
Here, teams
will end up being ['C', 'B', 'A']
because 'C' has the most first-place votes, followed by 'A' and 'B'. Since 'A' and 'B' never received a first-place vote, they are sorted by the number of second-place votes they received, in which 'B' beats 'A'. In a situation where 'B' and 'A' also had the same number of second-place votes, they would be sorted alphabetically, and 'A' would come before 'B'.
- Building the Final Ranking String: The final step is to concatenate the sorted teams into one string, which would be our final ranking based on the votes:
1result = ''.join(teams)
The result here would be 'CBA'
, which completes our example walkthrough. Team C is ranked first, team B is ranked second, and team A is ranked third based on the given votes.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def rankTeams(self, votes: List[str]) -> str:
5 # Get the length of a vote, which is the number of teams
6 num_teams = len(votes[0])
7
8 # Create a default dictionary to store the vote count for each position for each team
9 # The dictionary is initialized with lists of zeros, with the same length as the number of teams
10 vote_counts = defaultdict(lambda: [0] * num_teams)
11
12 # Count the votes for each position for each team
13 for vote in votes:
14 for rank, team in enumerate(vote):
15 vote_counts[team][rank] += 1
16
17 # Sort the teams based on their vote counts
18 # If vote counts are the same, fallback to lexicographical order (ASCII values)
19 # 'reverse=True' ensures a descending order since we want the highest voted team first
20 ranked_teams = sorted(votes[0], key=lambda team: (vote_counts[team], -ord(team)), reverse=True)
21
22 # Join the sorted teams into a string that represents their ranking
23 return "".join(ranked_teams)
24
1import java.util.Arrays;
2
3class Solution {
4 public String rankTeams(String[] votes) {
5 // The number of teams is determined by the length of a single vote string
6 int numTeams = votes[0].length();
7
8 // Create a 2D array to count the position based votes for each team (A-Z mapped to 0-25)
9 int[][] count = new int[26][numTeams];
10 for (String vote : votes) {
11 for (int i = 0; i < numTeams; ++i) {
12 // Increment the vote count for the team at the current position
13 count[vote.charAt(i) - 'A'][i]++;
14 }
15 }
16
17 // Create an array of Characters representing each team in the initial vote order
18 Character[] teams = new Character[numTeams];
19 for (int i = 0; i < numTeams; ++i) {
20 teams[i] = votes[0].charAt(i);
21 }
22
23 // Sort the array of teams based on the vote counts and then by alphabetical order
24 Arrays.sort(teams, (a, b) -> {
25 int indexA = a - 'A', indexB = b - 'A';
26 for (int k = 0; k < numTeams; ++k) {
27 // Compare the vote count for the current position
28 int difference = count[indexA][k] - count[indexB][k];
29 if (difference != 0) {
30 // If there's a difference, return the comparison result
31 return difference > 0 ? -1 : 1;
32 }
33 }
34 // If all vote counts are equal, sort by alphabetical order
35 return a - b;
36 });
37
38 // Build the final ranking string based on the sorted array of teams
39 StringBuilder result = new StringBuilder();
40 for (char team : teams) {
41 result.append(team);
42 }
43 return result.toString();
44 }
45}
46
1#include <vector>
2#include <string>
3#include <algorithm>
4#include <cstring>
5
6class Solution {
7public:
8 // This method will process a vector of strings representing votes and
9 // return a string representing the rank of teams.
10 string rankTeams(vector<string>& votes) {
11 // First, get the number of teams from the first vote
12 int num_teams = votes[0].size();
13
14 // Initialize a 2D array to keep track of the count of ranks for each team
15 int rank_count[26][num_teams];
16 memset(rank_count, 0, sizeof rank_count);
17
18 // Iterate over each vote and increment the count for team's rank position
19 for (auto& vote : votes) {
20 for (int i = 0; i < num_teams; ++i) {
21 rank_count[vote[i] - 'A'][i]++;
22 }
23 }
24
25 // Start with an initial ordering of teams as in the first vote
26 string ranking = votes[0];
27
28 // Sort the teams according to their rank counts
29 sort(ranking.begin(), ranking.end(), [&](auto& a, auto& b) {
30 // Retrieve the rank array indices corresponding to the teams
31 int team1_idx = a - 'A', team2_idx = b - 'A';
32
33 // Iterate over each rank position
34 for (int rank = 0; rank < num_teams; ++rank) {
35 // If count for a rank position is different, determine order by the higher count
36 if (rank_count[team1_idx][rank] != rank_count[team2_idx][rank]) {
37 return rank_count[team1_idx][rank] > rank_count[team2_idx][rank];
38 }
39 }
40
41 // If the teams are tied in all rank positions, order alphabetically
42 return a < b;
43 });
44
45 // Return the final ranking string
46 return ranking;
47 }
48};
49
1// Define a function that processes an array of strings representing votes
2// and returns a string representing the rank of teams.
3function rankTeams(votes: string[]): string {
4 // Get the number of teams from the size of the first vote
5 const numTeams = votes[0].length;
6
7 // Initialize a 2D array to keep track of the count of ranks for each team
8 const rankCount: number[][] = Array.from({ length: 26 }, () => new Array(numTeams).fill(0));
9
10 // Iterate over each vote and increment the count for team's rank position
11 for (let vote of votes) {
12 for (let i = 0; i < numTeams; i++) {
13 const teamIndex = vote.charCodeAt(i) - 'A'.charCodeAt(0);
14 rankCount[teamIndex][i]++;
15 }
16 }
17
18 // Start with an initial ordering of teams as in the first vote
19 let ranking = votes[0].split('');
20
21 // Sort the teams according to their rank counts
22 ranking.sort((a, b) => {
23 const team1Index = a.charCodeAt(0) - 'A'.charCodeAt(0);
24 const team2Index = b.charCodeAt(0) - 'A'.charCodeAt(0);
25
26 // Compare the teams based on their rank counts
27 for (let rank = 0; rank < numTeams; rank++) {
28 if (rankCount[team1Index][rank] !== rankCount[team2Index][rank]) {
29 return rankCount[team1Index][rank] > rankCount[team2Index][rank] ? -1 : 1;
30 }
31 }
32
33 // If the teams are tied in all rank positions, order alphabetically by comparing ASCII values
34 return a < b ? -1 : 1;
35 });
36
37 // Join the sorted array back into a string and return the final ranking string
38 return ranking.join('');
39}
40
41// Example Usage:
42const votes = ["ABC", "ACB", "ABC", "ACB", "ACB"];
43const ranking = rankTeams(votes);
44console.log(ranking); // Should print the team ranking based on the votes
45
Time and Space Complexity
Time Complexity
The time complexity of the provided code is determined by several factors:
-
Counting the rankings for each team involves iterating over all the votes and updating a list of size
n
, which is the number of teams. Each vote takesO(n)
time to iterate, and this is done for allm
votes. So, this part of the algorithm takesO(m * n)
time. -
Sorting the teams according to their rank counts and in case of a tie, using alphabetic ordering. Python's sort function uses TimSort, which has a worst-case time complexity of
O(n * log(n))
. Since there aren
teams, sorting them takesO(n * log(n))
time. -
Generating the final string involves creating a string from the sorted teams, which takes
O(n)
time.
Combining these factors, the overall time complexity is O(m * n + n * log(n) + n)
. Since n * log(n)
is likely to be the dominant term as n
grows in comparison to n
, we can approximate the time complexity as O(m * n + n * log(n))
.
Space Complexity
The space complexity of the code is determined by:
-
The space used by the
cnt
dictionary, which contains a list of counters, of sizen
, for each distinct team. Since there aren
teams, the total size of thecnt
dictionary isO(n^2)
. -
The space used by the sorting function could be
O(n)
in the worst case for the internal working storage during the sort.
Taking these into account, the overall space complexity of the algorithm is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.