Rank Teams by Votes

Medium

Atlassian

8 views

Topics:

ArraysStrings

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.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: 
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter, so their votes are used for the ranking.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English uppercase letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Rank Teams by Votes

Medium

Atlassian

8 views

Topics:

ArraysStrings

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.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: 
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter, so their votes are used for the ranking.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English uppercase letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you provide an example of the input votes array and the corresponding expected output, especially when there's a tie?
What is the maximum number of teams that can participate, and what is the maximum length of the votes array?
Is the input guaranteed to be valid, meaning will each vote string contain all teams exactly once, and will all votes have the same length?
If a team doesn't appear in any vote, should it be included in the output, and if so, how should it be ranked?
If there are multiple ties even after applying alphabetical order, what is the expected output?

Brute Force Solution

Approach

The brute force method for ranking teams by votes involves checking every single possible ranking order. We essentially explore all permutations of the teams to see which one best fits the given votes. It's like trying out every possible arrangement and then seeing which one feels the most right based on the rules.

Here's how the algorithm would work step-by-step:

First, generate all the possible orders the teams could be ranked in. Imagine writing down every possible list of the teams.
Then, for each of those possible ranking orders, go through each vote and see how well that vote agrees with that ranking order.
For a given vote, if the top team in the vote matches the top team in our ranked order, give that ranking order a point.
If the second team in the vote matches the second team in our ranked order, give that ranking order another point, and so on for each position in the vote and the ranking order.
Do this for every vote and every possible ranking order. This will let us see how many 'points' each ranking order received.
Finally, choose the ranking order that received the most points. That's our answer!

Code Implementation

def rank_teams_by_votes_brute_force(votes):
    if not votes:
        return ""

    teams = sorted(list(votes[0]))

    import itertools
    all_possible_rankings = list(itertools.permutations(teams))
    
    best_ranking = None
    highest_score = -1

    for possible_ranking in all_possible_rankings:
        current_score = 0
        
        # Evaluate ranking against all votes
        for vote in votes:
            for team_index, team in enumerate(possible_ranking):
                if team == vote[team_index]:
                    current_score += 1

        # Update best ranking if current one is better
        if current_score > highest_score:
            highest_score = current_score
            best_ranking = possible_ranking

    if best_ranking:
        return "".join(best_ranking)
    else:
        return "".join(teams)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n! * m * l) – The algorithm generates all possible permutations of teams, which takes O(n!) time, where n is the number of teams. For each permutation, it iterates through each vote (m votes) and compares each team in the vote to the ranking (length l, where l is the length of each vote, and l equals n, the number of teams). Therefore, the total time complexity is O(n! * m * l). Since l is equal to n, we could also say O(n! * m * n).

Space Complexity

O(P! * L) – The brute force approach generates all possible permutations of the teams, where P is the number of unique teams. Storing all these permutations requires O(P!) space, since there are P! possible rankings. Additionally, for each permutation, we're comparing it against each vote of length L. While the plain english description doesn't explicitly mention storing the votes, it implicitly requires holding onto them to compare against the generated rankings. Therefore the total auxiliary space used is proportional to the number of permutations multiplied by the length of the votes which is the number of teams. So, the space complexity becomes O(P! * L), where P is the number of unique teams and L is the length of a single vote (number of teams).

Optimal Solution

Approach

To efficiently rank teams by votes, we don't need to compare every single ranking combination. Instead, we'll tally each team's position in all the votes and then use these position tallies to sort the teams, prioritizing those with better average rankings.

Here's how the algorithm would work step-by-step:

First, we need to figure out all the unique teams that received votes. We'll keep track of these.
Next, we'll create a system to count where each team was ranked in all the different votes. For example, we'll count how many times a team was ranked first, second, third, and so on.
Now, we'll sort the teams based on these counts. Teams that were ranked higher more often will be placed higher in the ranking.
If two teams have the same count for a particular ranking, we'll move on to the next ranking position to see which team did better.
If all the ranking counts are the same for two teams, meaning they were equally ranked in all positions, we'll sort them alphabetically.
The final result is a list of teams ranked from best to worst based on their vote rankings.

Code Implementation

def rank_teams_by_votes(votes):
    if not votes:
        return ""

    teams = set()
    for vote in votes:
        for team in vote:
            teams.add(team)

    teams = sorted(list(teams))
    rank_length = len(votes[0])
    team_rank_counts = {}

    # Tally team rankings in each vote
    for team in teams:
        team_rank_counts[team] = [0] * rank_length

    for vote in votes:
        for rank, team in enumerate(vote):
            team_rank_counts[team][rank] += 1

    # Sort teams based on vote distribution and alphabetical order
    ranked_teams = sorted(teams, key=lambda team:
                           (team_rank_counts[team], team), reverse=True)

    # Convert list to string
    return "".join(ranked_teams)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n + nlogn) – Let n be the number of teams and m be the number of votes. Counting team positions involves iterating through all votes (m) and for each vote, processing each team (n), contributing O(m*n) complexity. Sorting the teams then involves comparing teams based on their counts, leading to O(nlogn) complexity where n is the number of teams. Therefore the overall time complexity is O(m*n + nlogn).

Space Complexity

O(M*C) – The space complexity is dominated by the data structure used to count the rank positions of each team, as well as the list of teams. We create a tally of each team's position in all votes. This tally can be viewed as a matrix with dimensions M x C, where M is the number of votes (length of the votes array), and C is the number of unique teams (length of each vote string). We also keep track of the unique teams to rank which takes O(C) space. Sorting the teams does not contribute significantly to the auxiliary space complexity. Therefore, the overall space complexity is O(M*C + C), which simplifies to O(M*C).

Edge Cases

Case	How to Handle
votes is null or empty	Return an empty string or handle the null case gracefully by returning an empty string; an empty input indicates no ranking is possible.
All votes are the same	The scoring matrix will have a high concentration of values in the first few columns, which the sorting algorithm must handle correctly, leading to an alphabetical tiebreaker.
Only one vote is provided	The result should be the teams in that single vote's order; the algorithm should work correctly with minimal data.
Votes have inconsistent team lengths (e.g., some have 'ABC', others 'AB')	Return only teams that appear in the first vote and ignore inconsistent rankings in other votes to maintain a standard set of teams.
Large number of votes and/or teams (performance considerations)	Use an efficient sorting algorithm (e.g., merge sort or quicksort) on the scoring matrix and alphabetical tiebreaker to handle potentially large inputs.
Teams are not all uppercase English letters	The code should be designed to work with any unique character set, or explicitly handle the possibility of invalid characters with appropriate error handling, or it must be stated that only uppercase letters will be used.
Ties in rankings require an alphabetical tiebreaker	Implement an alphabetical tiebreaker when two or more teams have the same score at each position, adding complexity to the comparison function.
votes contains empty strings	Ignore empty strings in the list of votes; an empty string implies no vote was cast for that entry, therefore it shouldn't impact rankings.