#1366

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Rank Teams by Votes

Rank Teams by Votes requires counting position-based votes and resolving ties with array scanning and hash lookup techniques efficiently.

array hash table string sorting counting

Problem Statement

You are given a list of strings votes, where each string represents a voter's ranking of all teams from highest to lowest. Each character in the string is a unique uppercase letter representing a team. Your task is to sort the teams based on the total votes received at each position, prioritizing higher positions first.

If two teams receive the same number of votes for a given position, the next lower position is used to break ties. If all positions are tied, teams are ranked alphabetically. Return a single string representing the teams in their final ranking order according to this voting system.

Examples

Example 1

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]

Output: "ACB"

Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team. Team B was ranked second by 2 voters and ranked third by 3 voters. Team C was ranked second by 3 voters and ranked third by 2 voters. As most of the voters ranked C second, team C is the second team, and team B is the third.

Example 2

Input: votes = ["WXYZ","XYZW"]

Output: "XWYZ"

X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.

Example 3

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]

Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"

Only one voter, so their votes are used for the ranking.

Constraints

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English uppercase letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Solution Approach

Count Votes by Position

Create a hash table or 2D array rank where rank[i][j] represents the number of votes team i received for position j. Scan each vote string, incrementing counts accordingly. This ensures we capture position-specific vote distribution.

Sort Teams Using Position Counts

Sort the teams by comparing their position counts starting from the first rank. If two teams tie at a position, compare counts for the next rank until all positions are considered. Use alphabetical order as a final tie-breaker for teams still tied after all positions.

Construct Result String

After sorting, concatenate the team letters in order into a single string. This string represents the final ranking according to the voting rules. This step is simple once the array scanning and sorting steps are correctly implemented.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(T * N + N log N) where T is the number of teams and N is the number of votes, due to scanning votes and sorting teams. Space complexity is O(T * T) for storing counts per team per position.

What Interviewers Usually Probe

Checks if you correctly implement position-based counting using an array or hash table.
Observes whether tie-breaking by subsequent positions and alphabet is handled accurately.
Looks for correct sorting logic combining count comparisons and alphabetical order.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count votes for all positions, not just first place.
Failing to implement proper tie-breaking logic across all positions.
Misordering alphabetically when teams remain tied after considering all positions.

Follow-up variants

Limiting team count to 10, which allows a fixed-size array approach.
Allowing partial votes where voters rank only some teams, requiring default zero counts.
Adding weighted votes where earlier positions carry more points, requiring modified counting logic.

FAQ

What is the main pattern used in Rank Teams by Votes?

The main pattern is array scanning combined with hash lookup to count votes for each team at each rank position.

How are ties resolved in Rank Teams by Votes?

Ties are resolved by comparing counts at the next lower position sequentially, and finally alphabetically if all positions are equal.

Can this solution handle all 26 teams efficiently?

Yes, by using a T x T array or hash table for counting votes, sorting remains efficient even at the maximum team count.

What is a common mistake when counting votes?

A common mistake is only counting first-place votes, ignoring how lower-rank votes affect tie-breaking.

How does GhostInterview assist with this problem?

GhostInterview guides implementation of position-based counting, correct sorting logic, and validates edge cases like ties and single-voter scenarios.

terminal

Solution

Solution 1: Counting + Custom Sorting

For each candidate, we can count the number of votes they receive at each rank, then compare the vote counts for different ranks in order. If the vote counts are the same, we compare the letters.

1

2

3

4

5

6

7

8

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        m = len(votes[0])
        cnt = defaultdict(lambda: [0] * m)
        for vote in votes:
            for i, c in enumerate(vote):
                cnt[c][i] += 1
        return "".join(sorted(cnt, key=lambda c: (cnt[c], -ord(c)), reverse=True))

Continue Practicing

#692 top k frequent words #1418 display table of food orders in a restaurant #1481 least number of unique integers after k removals