Rank Teams by Votes
Rank Teams by Votes is a medium heaps problem solved with the composite comparator pattern.
The best approach, optimal (count table + composite comparator), runs in O(n · m + m² log m) time and O(26 · m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recount inside the comparator) up.
Problem
In a ranked vote, each voter orders all competing teams from best to worst. Every team is a single uppercase letter, and votes[i] is the order chosen by voter i (its first character is that voter’s top team).
Teams are ranked by how many first places they received. If two teams tie on first places, compare their second places, then third places, and so on. If two teams are tied on every position, the team whose letter comes earlier in the alphabet ranks higher.
Return a string of all teams sorted by this ranking.
Examples
Example 1
- Input
votes = ["XYZ", "YXZ", "XZY", "YZX", "XYZ"]- Output
"XYZ"- Why
- X has three first places and Y two, so X leads. Z has no first places and comes last.
Example 2
- Input
votes = ["PQ", "QP"]- Output
"PQ"- Why
- P and Q tie on every position, so the alphabetical order decides.
Example 3
- Input
votes = ["ABCD", "BACD", "CDAB", "DCBA"]- Output
"CABD"- Why
- All four teams tie on first and second places. On third place C has two votes, A and B one each, D none. A and B also tie on fourth place, so A goes before B.
Constraints
1 <= votes.length <= 10001 <= votes[i].length <= 26- All
votes[i]have the same length and contain the same set of uppercase English letters. - Each vote lists every team exactly once.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recount inside the comparator) | O(m² · n · log m) | O(m) |
| Optimal (count table + composite comparator) | O(n · m + m² log m) | O(26 · m) |
1Brute force (recount inside the comparator)
O(m² · n · log m)The sort does O(m log m) comparisons, each scanning n votes for up to m positions.O(m)Only the list of m teams is stored.Sort the teams with a comparator that, for each position from first to last, scans all votes to count how often each of the two teams was placed there. The first position where the counts differ decides; if none does, alphabetical order decides.
- Take the teams from
votes[0]. - Comparator(a, b): for
posfrom 0 to m - 1, count votes withaatposand withbatpos; if different, the larger count wins. - If all positions tie, compare the letters.
- Sort and join the teams.
class Solution {
public String rankTeams(String[] votes) {
int m = votes[0].length();
List<Character> teams = new ArrayList<>();
for (char c : votes[0].toCharArray()) teams.add(c);
teams.sort((a, b) -> {
for (int pos = 0; pos < m; pos++) {
int ca = 0, cb = 0;
for (String v : votes) {
if (v.charAt(pos) == a) ca++;
if (v.charAt(pos) == b) cb++;
}
if (ca != cb) return cb - ca;
}
return a - b;
});
StringBuilder sb = new StringBuilder();
for (char c : teams) sb.append(c);
return sb.toString();
}
}class Solution:
def rankTeams(self, votes: List[str]) -> str:
from functools import cmp_to_key
m = len(votes[0])
def cmp(a: str, b: str) -> int:
for pos in range(m):
ca = cb = 0
for v in votes:
if v[pos] == a:
ca += 1
if v[pos] == b:
cb += 1
if ca != cb:
return cb - ca
return -1 if a < b else (1 if a > b else 0)
teams = sorted(votes[0], key=cmp_to_key(cmp))
return "".join(teams)class Solution {
public:
string rankTeams(vector<string>& votes) {
int m = votes[0].size();
string teams = votes[0];
sort(teams.begin(), teams.end(), [&](char a, char b) {
for (int pos = 0; pos < m; pos++) {
int ca = 0, cb = 0;
for (auto& v : votes) {
if (v[pos] == a) ca++;
if (v[pos] == b) cb++;
}
if (ca != cb) return ca > cb;
}
return a < b;
});
return teams;
}
};function rankTeams(votes) {
const m = votes[0].length;
const teams = votes[0].split("");
teams.sort((a, b) => {
for (let pos = 0; pos < m; pos++) {
let ca = 0, cb = 0;
for (const v of votes) {
if (v[pos] === a) ca++;
if (v[pos] === b) cb++;
}
if (ca !== cb) return cb - ca;
}
return a < b ? -1 : a > b ? 1 : 0;
});
return teams.join("");
}2Optimal (count table + composite comparator)
O(n · m + m² log m)Building the table reads every character of every vote once; the sort does O(m log m) comparisons of O(m) each.O(26 · m)The count table has 26 rows of m columns.Count once, up front, how many votes put each team at each position in a 26 x m table. Then sort the teams with a comparator that walks the two rows of the table: the first position with different counts decides (more votes first), and alphabetical order breaks a full tie.
- Fill
count[c - 'A'][pos]by scanning every vote once. - Sort the teams of
votes[0]: compare rows position by position, larger count first; if every position ties, the smaller letter first. - Join the sorted teams into the answer.
class Solution {
public String rankTeams(String[] votes) {
int m = votes[0].length();
int[][] count = new int[26][m];
for (String v : votes) {
for (int pos = 0; pos < m; pos++) count[v.charAt(pos) - 'A'][pos]++;
}
List<Character> teams = new ArrayList<>();
for (char c : votes[0].toCharArray()) teams.add(c);
teams.sort((a, b) -> {
for (int pos = 0; pos < m; pos++) {
int diff = count[b - 'A'][pos] - count[a - 'A'][pos];
if (diff != 0) return diff;
}
return a - b;
});
StringBuilder sb = new StringBuilder();
for (char c : teams) sb.append(c);
return sb.toString();
}
}class Solution:
def rankTeams(self, votes: List[str]) -> str:
m = len(votes[0])
count = {c: [0] * m for c in votes[0]}
for v in votes:
for pos, c in enumerate(v):
count[c][pos] += 1
teams = sorted(votes[0], key=lambda c: ([-x for x in count[c]], c))
return "".join(teams)class Solution {
public:
string rankTeams(vector<string>& votes) {
int m = votes[0].size();
vector<vector<int>> count(26, vector<int>(m, 0));
for (auto& v : votes) {
for (int pos = 0; pos < m; pos++) count[v[pos] - 'A'][pos]++;
}
string teams = votes[0];
sort(teams.begin(), teams.end(), [&](char a, char b) {
for (int pos = 0; pos < m; pos++) {
if (count[a - 'A'][pos] != count[b - 'A'][pos]) {
return count[a - 'A'][pos] > count[b - 'A'][pos];
}
}
return a < b;
});
return teams;
}
};function rankTeams(votes) {
const m = votes[0].length;
const count = Array.from({ length: 26 }, () => new Array(m).fill(0));
for (const v of votes) {
for (let pos = 0; pos < m; pos++) count[v.charCodeAt(pos) - 65][pos]++;
}
const teams = votes[0].split("");
teams.sort((a, b) => {
const ra = count[a.charCodeAt(0) - 65], rb = count[b.charCodeAt(0) - 65];
for (let pos = 0; pos < m; pos++) {
if (ra[pos] !== rb[pos]) return rb[pos] - ra[pos];
}
return a < b ? -1 : a > b ? 1 : 0;
});
return teams.join("");
}Edge cases to test
- A single vote: the answer is that vote
- Only one team: the answer is that single letter
- Teams tied on every position: break the tie alphabetically
- Two teams tied on first places but split on second places: the second place decides
Hints
Hint 1
For every team, count how many times it was placed at each position: count[team][pos].
Hint 2
Compare two teams by walking positions from 0 upward; the first position where their counts differ decides, larger count first.
Hint 3
Sort the letters of the first vote with that comparator, falling back to alphabetical order when all counts match.
FAQ
What is the best time complexity for Rank Teams by Votes?
Optimal (count table + composite comparator) runs in O(n · m + m² log m) time and O(26 · m) extra space. Building the table reads every character of every vote once; the sort does O(m log m) comparisons of O(m) each.
Which pattern does Rank Teams by Votes use?
It is a heaps problem that uses the composite comparator pattern. Other problems with the same pattern: Top K Frequent Elements, Design Task Manager, Design Movie Rental System.
Is there a brute force solution for Rank Teams by Votes?
Yes. Brute force (recount inside the comparator) takes O(m² · n · log m) time and O(m) space. Sort the teams with a comparator that, for each position from first to last, scans all votes to count how often each of the two teams was placed there.
Which edge cases should I test for Rank Teams by Votes?
A single vote: the answer is that vote; Only one team: the answer is that single letter; Teams tied on every position: break the tie alphabetically; Two teams tied on first places but split on second places: the second place decides.