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 <= 10001 <= votes[i].length <= 26votes[i].length == votes[j].length for 0 <= i, j < votes.length.votes[i][j] is an English uppercase letter.votes[i] are unique.votes[0] also occur in votes[j] where 1 <= j < votes.length.This approach involves counting the votes each team receives for each position. We store these counts in a dictionary, where each team has a list representing its vote count for each position. Then, by sorting the teams based on these counts (and alphabetically in case of ties), we can determine the final ranking.
We initialize a 2D array to keep track of how many votes each team receives for each ranking position. We iterate through each vote to populate this array. Then, we sort the teams using a custom comparator that first compares based on vote counts, breaking ties alphabetically if necessary.
C++
Java
Python
C#
JavaScript
The time complexity is O(N * P * log(P)), where N is the number of votes and P is the number of positions (or teams). The space complexity is O(P^2) due to the vote count storage.
This approach defines a custom comparator function to sort the teams according to the given ranking rules. We count the votes similarly, but rather than sorting explicitly with nested loops, we rely on a sophisticated comparator that resolves conflicts directly during the sorting process.
This solution sets up a custom struct and comparator for sorting teams based on the detailed voting rules. We use qsort with a comparator function to handle the sorting of voteRank objects of teams.
C++
Java
Python
C#
JavaScript
O(P * log(P)) is the time complexity, and O(P) for space due to temporary storage and object sorting.
| Approach | Complexity |
|---|---|
| Counting Votes by Position | The time complexity is O(N * P * log(P)), where N is the number of votes and P is the number of positions (or teams). The space complexity is O(P^2) due to the vote count storage. |
| Using a Custom Comparator | O(P * log(P)) is the time complexity, and O(P) for space due to temporary storage and object sorting. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,627 views views
Watch 9 more video solutions →Practice Rank Teams by Votes with our built-in code editor and test cases.
Practice on FleetCode