Rank Teams by Ballots
MediumSorting & Searching
Problem
Judges at a robotics fair each submit a ballot ranking every team from first to last; teams are single uppercase letters and a ballot is a string such as "BCA" (B first, C second, A third). All ballots rank the same set of teams.
Teams are ordered by how many first-place votes they received (more is better). Ties are broken by second-place votes, then third-place votes, and so on. If two teams are tied at every position, the team with the earlier letter in the alphabet goes first. Return the final ranking as a string.
Example 1
- Input:
- ballots = ["BCA", "CAB", "BAC"]
- Output:
- "BCA"
B has two first places, C one, A none. So B, then C, then A.
Example 2
- Input:
- ballots = ["XYZ", "ZYX"]
- Output:
- "XZY"
X and Z both have one first place and one third place, so the letter decides: X before Z. Y has no first place.
Constraints
- 1 ≤ ballots.length ≤ 1000
- 1 ≤ ballots[i].length ≤ 26
- Every ballot is a permutation of the same set of uppercase letters.
Hint
Show the first hint
Each team can be summarised by a vector: how many votes it got at position 0, position 1, ...
Walkthrough
How to approach it
01Clarify before coding
- Do all ballots contain every team? Yes, each is a permutation of the same letters.
- What breaks a complete tie? The alphabetical order of the letters.
- How many teams? At most 26, so a vector of size 26 per team is cheap.
02Brute force
In the comparator, scan all ballots to count each team's votes at each position on demand.
Cost: O(t log t · b · t) for t teams and b ballots: wasteful recounting at every comparison.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.