1366. Rank Teams by Votes

MediumArrayHash TableStringCountingSorting
Leetcode Link

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:

  1. Primary Criterion: A team is ranked higher if it has received more first-place votes compared to other teams.
  2. Tiebreaker: If teams tie for first-place votes, then second-place votes are compared, and so forth, until the tie is broken.
  3. 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:

  1. 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 size n to hold the counts of being voted for each rank from 1 to n.

  2. 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.
  3. 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:

  1. 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 function lambda: [0] * n ensures that any new key (representing a team) in the dictionary automatically starts with an array of zeros, where n is the number of teams.

  2. 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 incrementing cnt[c][i] where c is the team, we accumulate the rank votes for every team.

  3. 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), where x 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 because sorted 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.

  4. 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 use reverse=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.

  5. 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 Evaluator

Example 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.

  1. 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.

  1. 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.

  1. 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'.

  1. 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:

  1. 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 takes O(n) time to iterate, and this is done for all m votes. So, this part of the algorithm takes O(m * n) time.

  2. 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 are n teams, sorting them takes O(n * log(n)) time.

  3. 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:

  1. The space used by the cnt dictionary, which contains a list of counters, of size n, for each distinct team. Since there are n teams, the total size of the cnt dictionary is O(n^2).

  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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄