Rank Teams by Votes

Rank teams by per-position vote tallies, ties broken by team name.

Medium
Time O(N * L) Space O(L^2)
LeetCode
4 min read
hash-map sorting counting

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
Build a map 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#

Rank Teams by Votes
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.