Solution: Rank Teams by Votes

Statement

Assume a ranking system where each gives a rank to all competing teams from highest to lowest. The final ranking is decided on the basis of the number of first-place votes they receive. If there’s a tie for first place, the second-place votes are used to break the tie; if there’s still a tie, the third-place votes are considered, and this continues until all positions have been evaluated. If teams remain tied after all positions have been reviewed, they are ranked alphabetically by their team names.

Given an array of strings votes that represents the rankings given by all voters, sort the teams according to the specified ranking system and return a string that lists all the teams in the ranked order.

Constraints:

• $1 \leq$ votes.length $\leq 1000$

• $1 \leq$ votes[i].length $\leq 26$

• votes[i].length == votes[j].length for $0 \leq$ i, j $<$ votes.length

• votes[i][j] is an uppercase English letter.

• All characters of votes[i] are unique.

• All characters present in votes[0] are also found in votes[i] where $1 \leq$ i $<$ votes.length.

Solution

The key intuition for solving this problem is to efficiently keep track of the vote counts each team receives for each position. We create a 2D array for this purpose, where the rows represent the teams and the columns represent the vote counts for each position. For each team in votes[i][j], we update its vote count at the $j^{th}$ index in the counts array. After processing all votes, we sort the counts array based on the values in each row, prioritizing the row with the lowest value at the first index. If there is a tie, the row with the lowest value at the second index takes precedence, and so on. The final result is constructed using team's name corresponding to each row in the sorted array.

Using the above intuition, the solution can be implemented as follows:

1. Create a 2D array counts with dimensions $26 \times 27$ to store vote counts for each team.

   1. The first dimension ($26$) corresponds to the teams (A–Z), as there can be a maximum of $26$ teams.

   2. The second dimension ($27$) holds the vote counts for each rank. Because there can be a maximum of $26$ teams, the maximum rank a team can get is $26$. It includes an additional column to store the team’s name to ensure that we don’t lose track of which team’s data is in each row after sorting.

2. For each team index t, store the team’s name at counts[t][26]. This keeps track of which team corresponds to each row in the counts array.

3. Start iterating through each string votes[i] to process the ranking given by each voter.

4. For each character votes[i][j] representing a team in the vote, decrement its rank in the counts. This is because each row in counts denotes the rank of a team; a lower count indicates a higher rank.

5. Sort the counts array based on the values in each row. The sorting is done such that the row with the lowest value at the first index comes first. If there is a tie, the row with the lowest value at the second index takes precedence, and so on.

6. Construct the final result by retrieving the team name stored at the last index (counts[i][26]) in the sorted counts.

7. Return the constructed result, which contains all teams sorted according to the specified ranking system.

Let’s look at the following illustration to get a better understanding of the solution: