Leetcode 1366. Rank Teams by Votes

Problem Explanation

Given a list of votes for teams, we need to sort the teams according to a special ranking system. Each voter gives a rank from highest to lowest to all teams participated in the competition. The ordering of teams is decided by which team received the most position-one votes. If two or more teams tie in first position, we consider the second position to resolve conflict, continuing this process if ties persist. If teams still exhibit a tie after considering all positions, they are ranked alphabetically.

Approach

To implement this, we can utilize the concepts of Priority Queue and Hash Table. The idea is to store the frequency of ranks for each team in a hash table. So we can initialize a list of 26 teams with 'A' to 'Z' as their names and a rank counter. Then for each vote, we increase the rank counter for the team according to their rank in the vote.

Next, we sort these teams. If teams have the same rank count, we rank them based on their names (alphabetically). Once sorted, we can return the string of all the team names, which gives us the final result.

Example

Let's walkthrough this approach with "ABC","ACB","ABC","ACB","ACB" as our votes. With five votes total, team A is ranked first on each one. So, A should come first.

When considering the next rank, B and C are tied with 2 first-place votes each. Looking at second-place votes next, B only has two while C has three. This puts C ahead of B and thus our output becomes ACB.

Python Solution

1
2python 
3class Solution:
4    def rankTeams(self, votes: List[str]) -> str:
5        count = {v: [0] * len(votes[0]) + [v] for v in votes[0]}
6        for vote in votes:
7            for i, v in enumerate(vote):
8                count[v][i] -= 1  # subtract because Python sorts in ascending
9        return ''.join(sorted(votes[0], key=count.get))

Java Solution

1
2java
3public class Solution {
4    public String rankTeams(String[] votes) {
5        if(votes.length == 1)
6            return votes[0];
7        int[][] teamFrequency = new int[26][26];
8        char[] teams = votes[0].toCharArray();
9        for(String vote : votes) {
10            char[] ranking = vote.toCharArray();
11            for(int i = 0; i < ranking.length; i++) {
12                teamFrequency[ranking[i] - 'A'][i]++;
13            }
14        }
15        Comparator<Character> cmp = (a, b) -> {
16            for(int i = 0; i <= 26; i++) {
17                if(teamFrequency[a - 'A'][i] != teamFrequency[b - 'A'][i]) {
18                    return teamFrequency[b - 'A'][i] - teamFrequency[a - 'A'][i];
19                }
20            }
21            return a - b;
22        };
23        Character[] resultChar = new Character[teams.length];
24        for(int i = 0; i < teams.length; i++)
25            resultChar[i] = teams[i];
26        Arrays.sort(resultChar, cmp);
27        StringBuilder sb = new StringBuilder();
28        for (char c : resultChar)
29            sb.append(c);
30        return sb.toString();
31    }
32}

JavaScript Solution

1
2javascript
3class Solution{
4    rankTeams(votes) {
5        let n = votes[0].length;
6        let voteCounts = {};
7        for(let vote of votes) {
8            for(let i = 0; i < n; i++) {
9                if(!voteCounts[vote[i]])
10                    voteCounts[vote[i]] = Array(n).fill(0);
11                voteCounts[vote[i]][i]--;
12            }
13        }
14        return [...votes[0]].sort((a, b) => {
15            let compare = voteCounts[a].join('').localeCompare(voteCounts[b].join(''));
16            return compare === 0 ? a.localeCompare(b) : compare;
17        }).join('');
18    }
19}

C++ Solution

1
2C++
3class Solution {
4public:
5    struct team{
6        int t[26] = {0};
7        int name;
8        bool operator<(const team& op2)const{
9            for(int i = 0; i<26 ; i++)
10                if(t[i]!=op2.t[i])
11                    return t[i]<op2.t[i];
12            return name>op2.name;
13        }
14    };
15    string rankTeams(vector<string>& votes) {
16        int n = votes[0].size();
17        vector<team>ke(26);
18        for(int i = 0 ; i<26 ; i++) ke[i].name = i;
19        for(auto c : votes)
20            for(int i = 0 ; i<n ; i++)
21            ke[c[i]-'A'].t[i]--;
22        sort(ke.begin(),ke.begin()+n);
23        string ans = "";
24        for(int i = 0 ; i<n ; i++) ans += ke[i].name+'A';
25        return ans;
26    }
27};

C# Solution

1
2csharp
3public class Solution {
4    public string RankTeams(string[] votes) {
5        if(votes.Length == 1)
6            return votes[0];
7        int[][] teamFrequency= new int[26][];
8        for (int i = 0; i < 26; i++)
9        {
10            teamFrequency[i] = new int[26];
11        }
12        char[] teams = votes[0].ToCharArray();
13        foreach(string vote in votes){
14            char[] ranking = vote.ToCharArray();
15            for(int i = 0; i < ranking.Length; i++ ){
16                teamFrequency[ranking[i] - 'A'][i]++;
17            }
18        }
19     Array.Sort(teams, (a, b) => {
20            for(int i = 0; i <= 26; i++)
21                if(teamFrequency[b - 'A'][i] != teamFrequency[a - 'A'][i])
22                    return teamFrequency[b - 'A'][i] - teamFrequency[a - 'A'][i];
23                return a - b; 
24        });
25        return new string(teams);
26    }
27}

Explanation

The Python solution uses a hash table count to store a list of scores for each team. The ith score of a team is the count of votes it gets for the ith position. To do that, it is assumed that the votes for the ith position will be negative because Python sorts in ascending order by default.

The Java solution is similar to the Python solution but has to implement more coding for sorting than Python, due to the difference in language features. In Java, we sort the array in descending order for which we have to specify a custom comparator. Java doesnโ€™t allow sorting list of arrays by default as Python does. It sorts character array using the custom comparator defined inside the function.

The JavaScript solution is almost the same as python except using array instead of dictionary for storing count. We have to manually sort the array because JavaScript doesnโ€™t support sorting array as Python does. Here, we apply localeCompare to compare strings and it provides more flexibility and capability than the simple alphabetical order of ASCII values of characters which other languages provide.

The C++ solution is somewhat different compared to other languages' solutions by structuring each team as a structure of teams with the rank count of each position of the team and the name of the team itself. All the teams are grouped together and sorted as per the requirement.

The C# solution follows the same path as the Java solution but with a different syntax.

Conclusion

Every solution tackles this problem by using a similar approach at their core. Nevertheless, the programming languages differ in their syntax and specific built-in methods, which influences how we implement this approach in unique ways across the different languages. This comparison demonstrates how different programming languages can impact the coding process and the efficiency of our solution.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ