Rank Teams by Votes

Medium Heaps Composite comparator Original on LeetCode

Reported atAtlassian

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 <= 1000
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(m² · n · log m)The sort does O(m log m) comparisons, each scanning n votes for up to m positions.
SpaceO(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.

  1. Take the teams from votes[0].
  2. Comparator(a, b): for pos from 0 to m - 1, count votes with a at pos and with b at pos; if different, the larger count wins.
  3. If all positions tie, compare the letters.
  4. 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();
    }
}

2Optimal (count table + composite comparator)

TimeO(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.
SpaceO(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.

  1. Fill count[c - 'A'][pos] by scanning every vote once.
  2. Sort the teams of votes[0]: compare rows position by position, larger count first; if every position ties, the smaller letter first.
  3. 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();
    }
}

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.