Rank Teams by Votes
Rank teams by per-position vote tallies, ties broken by team name.
Problem#
Each voter submits a permutation of team names. The final ranking compares teams by their vote count at position 1; ties go to votes at position 2; and so on. Final tiebreaker: alphabetical order of the team name. Return the final ranking as a string.
Examples#
votes = ["ABC","ACB","ABC","ACB","ACB"]→"ACB".votes = ["WXYZ","XYZW"]→"XWYZ".
Constraints#
1 <= votes.length <= 1000, all votes are same-length permutations of uppercase letters.
Hints#
Hint
team -> [votesAtPos0, votesAtPos1, ...] then sort by the vector with team-name tiebreak. Approach#
Aggregate score[team][pos] = count from all ballots. Sort the teams by their full score vector descending; on a full tie use alphabetical ascending team name.
Solution#
class Solution {public: string rankTeams(vector<string>& votes) { int L = votes[0].size(); unordered_map<char, vector<int>> score; for (auto& v : votes) { for (int i = 0; i < L; ++i) { if (!score.count(v[i])) score[v[i]] = vector<int>(L, 0); ++score[v[i]][i]; } } string teams = votes[0]; sort(teams.begin(), teams.end(), [&](char a, char b) { const auto& sa = score[a]; const auto& sb = score[b]; for (int i = 0; i < L; ++i) if (sa[i] != sb[i]) return sa[i] > sb[i]; return a < b; }); return teams; }};func rankTeams(votes []string) string { L := len(votes[0]) score := map[byte][]int{} for _, v := range votes { for i := 0; i < L; i++ { c := v[i] if _, ok := score[c]; !ok { score[c] = make([]int, L) } score[c][i]++ } } teams := []byte(votes[0]) sort.Slice(teams, func(i, j int) bool { a, b := teams[i], teams[j] sa, sb := score[a], score[b] for k := 0; k < L; k++ { if sa[k] != sb[k] { return sa[k] > sb[k] } } return a < b }) return string(teams)}from typing import List
class Solution: def rankTeams(self, votes: List[str]) -> str: L = len(votes[0]) score: dict = {} for v in votes: for i, c in enumerate(v): if c not in score: score[c] = [0] * L score[c][i] += 1 teams = list(votes[0]) # Sort by descending score vector, then ascending team name. teams.sort(key=lambda c: ([-x for x in score[c]], c)) return ''.join(teams)function rankTeams(votes) { const L = votes[0].length; const score = new Map(); for (const v of votes) { for (let i = 0; i < L; i++) { const c = v[i]; if (!score.has(c)) score.set(c, new Array(L).fill(0)); score.get(c)[i]++; } } const teams = [...votes[0]]; teams.sort((a, b) => { const sa = score.get(a); const sb = score.get(b); for (let i = 0; i < L; i++) { if (sa[i] !== sb[i]) return sb[i] - sa[i]; } return a < b ? -1 : a > b ? 1 : 0; }); return teams.join('');}class Solution { public String rankTeams(String[] votes) { int L = votes[0].length(); Map<Character, int[]> score = new HashMap<>(); for (String v : votes) { for (int i = 0; i < L; i++) { char c = v.charAt(i); score.computeIfAbsent(c, k -> new int[L])[i]++; } } Character[] teams = new Character[L]; for (int i = 0; i < L; i++) teams[i] = votes[0].charAt(i); Arrays.sort(teams, (a, b) -> { int[] sa = score.get(a); int[] sb = score.get(b); for (int i = 0; i < L; i++) { if (sa[i] != sb[i]) return sb[i] - sa[i]; } return Character.compare(a, b); }); StringBuilder sb = new StringBuilder(); for (char c : teams) sb.append(c); return sb.toString(); }}function rankTeams(votes: string[]): string { const L = votes[0].length; const score = new Map<string, number[]>(); for (const v of votes) { for (let i = 0; i < L; i++) { const c = v[i]; if (!score.has(c)) score.set(c, new Array<number>(L).fill(0)); (score.get(c) as number[])[i]++; } } const teams: string[] = [...votes[0]]; teams.sort((a: string, b: string): number => { const sa = score.get(a) as number[]; const sb = score.get(b) as number[]; for (let i = 0; i < L; i++) { if (sa[i] !== sb[i]) return sb[i] - sa[i]; } return a < b ? -1 : a > b ? 1 : 0; }); return teams.join('');}Editorial#
The teams are exactly the characters of any single ballot (every ballot is a permutation). Sorting them with a custom comparator that walks score vectors gives the correct rank. The terminal a < b tiebreak ensures determinism when scores are identical across all positions.
Complexity#
- Time: O(N * L + L^2 log L).
- Space: O(L^2).
Concept revision#
Related#