LeetCode 1366. Rank Teams by Votes – Java
Problem Statement
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.
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 was ranked third by 3 voters. Team C was ranked second by 3 voters and was 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 tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.
Example 3:
Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"] Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK" Explanation: Only one voter so his votes are used for the ranking.
Constraints:
1 <= votes.length <= 10001 <= votes[i].length <= 26votes[i].length == votes[j].lengthfor0 <= 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 invotes[j]where1 <= j < votes.length.
Solution
- First add all the candidates to a list from first vote.
- Build rank matrix – ranking[i][j] is the number of votes for team j to be the i-th rank
- Sort candidates based on rank on ranking[i][j].
Code
class Solution {
public String rankTeams(String[] votes) {
if(votes.length == 0)
return "";
int totalRanks = votes[0].length();
List<Character> allCandidates = strToList(votes[0]);
/*
* Build rank matrix - ranking[i][j] is the number of votes for team j to be the
* i-th rank
*/
int[][] ranking = new int[totalRanks][26];
for (String v : votes) {
for (int i = 0; i < v.length(); i++) {
ranking[i][v.charAt(i) - 'A']++;
}
}
/* Sort team list using the ranking matrix based on tie-breaking rule */
allCandidates.sort(new Comparator<Character>() {
@Override
public int compare(Character c1, Character c2) {
for (int i = 0; i < totalRanks; i++) {
if (ranking[i][c1 - 'A'] != ranking[i][c2 - 'A']) {
return ranking[i][c2 - 'A'] - ranking[i][c1 - 'A'];
}
}
return c1 - c2;
}
});
return listToString(allCandidates);
}
private List<Character> strToList(String str) {
List<Character> list = new ArrayList<>();
for (char ch : str.toCharArray()) {
list.add(ch);
}
return list;
}
private String listToString(List<Character> candidates) {
StringBuilder sb = new StringBuilder();
for (Character ch : candidates) {
sb.append(ch);
}
return sb.toString();
}
}
