🌱 Keegan's Digital Garden

1366. Rank Teams by Votes

2 min read

📝 Problem Details

input vector<string> votes sort all teams according to the ranking system order by frequency of position 1 votes go and check number position 2 votes if there is a tie go and check number of position 3 votes if there is another tie rank them alphabetically after that if there is still a tie return a string of all teams sorted by their rank

💡 Explanation of Solution

- create a map where:
	- key is a character representing a team
	- value is a vector of integers counting votes for each position (0-based index)

- for each vote string:
	- increment the count for each team at their respective positions

- sort the result using a custom comparator that:
	- first compares teams based on vote counts at each position, starting from position 0
	- if there's a tie for all positions, sorts alphabetically

⌛ Complexity Analysis

Time Complexity: O(1) since we have an upper bound of 26 being the number of possible characters to count and sort votes for

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        if (votes.empty()) return "";
        if (votes.size() == 1) return votes[0];
        
        int n = votes[0].length(); // Number of teams
        
        // Use a map where:
        // - Key: team character
        // - Value: vector of vote counts at each position
        map<char, vector<int>> teamRanks;
        
        // Initialize the team rankings
        for (char c : votes[0]) {
            teamRanks[c] = vector<int>(n, 0);
        }
        
        // Count the votes for each team at each position
        for (const string& vote : votes) {
            for (int i = 0; i < n; i++) {
                char team = vote[i];
                teamRanks[team][i]++;
            }
        }
        
        // Create a string with all teams for sorting
        string result = votes[0];
        
        // Sort the result string using the team ranks
        // We have to use a custom comparator here because we need
        // to sort by vote counts first, not by team characters
        sort(result.begin(), result.end(), [&](char a, char b) {
            // Compare vote counts at each position
            for (int i = 0; i < n; i++) {
                if (teamRanks[a][i] != teamRanks[b][i]) {
                    return teamRanks[a][i] > teamRanks[b][i]; // Higher votes come first
                }
            }
            // If all positions have equal votes, sort alphabetically
            return a < b;
        });
        
        return result;
    }
};

Graph View