Rank Teams by Votes – C++ Solution

Problem Description

Ah, the age-old dilemma of ranking teams based on votes! Imagine you’re at a sports event, and everyone is shouting for their favorite team. But instead of a simple cheer-off, we have a sophisticated voting system. The problem is to rank these teams based on the votes they receive. Sounds simple, right? Well, it’s like trying to decide who gets the last slice of pizza when everyone has a different opinion.

In this problem, you are given a list of votes, where each vote is a string representing the order of preference for the teams. Your task is to rank the teams based on these votes. The team with the highest rank in the most votes gets to bask in the glory of being number one.

Code Solution


struct Team {
  char name;
  vector rank;
  Team(char name, int teamSize) : name(name), rank(teamSize) {}
};

class Solution {
 public:
  string rankTeams(vector& votes) {
    const int teamSize = votes[0].size();
    string ans;
    vector teams;

    for (int i = 0; i < 26; ++i)
      teams.push_back(Team('A' + i, teamSize));

    for (const string& vote : votes)
      for (int i = 0; i < teamSize; ++i)
        ++teams[vote[i] - 'A'].rank[i];

    ranges::sort(teams, [](const Team& a, const Team& b) {
      return a.rank == b.rank ? a.name < b.name : a.rank > b.rank;
    });

    for (int i = 0; i < teamSize; ++i)
      ans += teams[i].name;

    return ans;
  }
};

Approach

The approach taken in this solution is straightforward yet effective. We first create a Team structure to hold the name of the team and its ranking based on the votes. We initialize a vector of teams, each represented by a letter from 'A' to 'Z'.

Next, we iterate through the votes, updating the rank of each team based on their position in the votes. After tallying the votes, we sort the teams based on their ranks. If two teams have the same rank, we sort them alphabetically by their names. Finally, we construct the result string by appending the names of the teams in their ranked order.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M + M log M), where N is the number of votes and M is the number of teams.
Space Complexity	O(M), where M is the number of teams, as we store the ranks in a vector.

Real-World Example

Imagine a talent show where judges vote for their favorite performers. Each judge ranks the performers, and at the end of the show, the performer with the highest cumulative rank wins. This problem mimics that scenario perfectly, where we need to tally the votes and determine the winner based on the rankings provided by the judges.