Problem Description

The "Rank Teams by Votes" problem asks you to determine the final ranking of teams based on votes from multiple voters. Each vote is a string where the order of characters represents the voter's ranking of the teams. For instance, in the vote "ABC", team 'A' is ranked 1st, 'B' is 2nd, and 'C' is 3rd by that voter.

The rules for ranking are as follows:

• For each position (1st, 2nd, 3rd, ...), the team with more votes in that position ranks higher.
• If two teams have the same number of votes in the first position, compare the number of votes in the second position, and so on.
• If teams are still tied after considering all positions, they are ranked alphabetically by their team letter.

The output should be a single string representing the final ranking of teams from highest to lowest.

Thought Process

At first glance, the problem seems to require comparing the frequency of each team's appearances at each rank, position by position. A brute-force approach might involve comparing every team against every other team for each position, but this would be inefficient and difficult to maintain.

Instead, it's helpful to think about the problem as a sorting task, where the "key" for sorting each team is an array of counts: how many times was this team voted 1st, 2nd, 3rd, etc. This leads to a more efficient, structured approach:

• Count the votes for each team at each position.
• Sort the teams by their vote counts at each position, using alphabetical order as a tiebreaker.

Solution Approach

Let's break down the solution into clear steps:

1. Initialize Vote Counters:
   • Create a dictionary (hash map) where each team maps to a list of counts, one for each possible rank position. For example, if there are 4 teams, each team will have a list of 4 integers.
2. Count the Votes:
   • For each vote string, iterate through each character and its index. For each character (team), increment the count at the corresponding position in its list.
3. Sort the Teams:
   • Sort the team letters using a custom key: for each team, use their list of counts (negated to sort descending), and finally the team letter itself for alphabetical order as a tiebreaker.
   • This ensures that teams with more votes in earlier positions come first, and ties are broken alphabetically.
4. Return the Result:
   • Join the sorted team letters into a single string for the result.

This approach leverages hash maps for fast counting and custom sorting for ranking, making it efficient and easy to follow.

Example Walkthrough

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

1. Step 1: Initialize Vote Counters
   Teams: A, B, C. Each gets an array of 3 zeros: [0, 0, 0]
2. Step 2: Count Votes
   • First vote: A B C → A[0]+=1, B[1]+=1, C[2]+=1
   • Second vote: A C B → A[0]+=1, C[1]+=1, B[2]+=1
   • Third vote: A B C → A[0]+=1, B[1]+=1, C[2]+=1
   • Fourth vote: A C B → A[0]+=1, C[1]+=1, B[2]+=1
   • Fifth vote: A C B → A[0]+=1, C[1]+=1, B[2]+=1
   After tallying:
   • A: [5, 0, 0]
   • B: [0, 2, 3]
   • C: [0, 3, 2]
3. Step 3: Sort Teams
   • Compare by first element: A has 5, B and C have 0. So A is first.
   • B vs C: Compare second element, B has 2, C has 3. So C is second, B is third.
   Final order: A, C, B
4. Step 4: Return Result
   Output: "ACB"

Time and Space Complexity

Brute-force Approach:
If you compared every team against every other team for every position, the complexity would be O(n^2 * k), where n is the number of teams and k is the number of positions. This would be inefficient for larger inputs.

Optimized Approach:

• Counting votes: O(m * n), where m is the number of votes and n is the number of teams (positions in each vote).
• Sorting: O(n log n), since we sort the n teams with a custom comparator.
• Total: O(mn + n log n)
• Space: O(n^2) for the vote counts (since each team stores an array of size n).

Summary

The "Rank Teams by Votes" problem is elegantly solved by counting each team's votes per position and sorting with a custom comparator that considers all positions and uses alphabetical order as a tiebreaker. This method is both efficient and easy to reason about, leveraging hash maps for counting and stable sorting for ranking. The clear separation of counting and sorting makes the solution robust and maintainable.

Code Implementation

from collections import defaultdict

class Solution:
    def rankTeams(self, votes):
        if not votes:
            return ""
        n = len(votes[0])
        count = defaultdict(lambda: [0]*n)
        for vote in votes:
            for i, team in enumerate(vote):
                count[team][i] += 1
        teams = list(votes[0])
        teams.sort(key=lambda team: ([-c for c in count[team]], team))
        return ''.join(teams)
      

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        if (votes.empty()) return "";
        int n = votes[0].size();
        unordered_map<char, vector<int>> count;
        for (const string& vote : votes) {
            for (int i = 0; i < n; ++i) {
                count[vote[i]].resize(n, 0);
                count[vote[i]][i]++;
            }
        }
        vector<char> teams(votes[0].begin(), votes[0].end());
        sort(teams.begin(), teams.end(), [&count, n](char a, char b) {
            for (int i = 0; i < n; ++i) {
                if (count[a][i] != count[b][i])
                    return count[a][i] > count[b][i];
            }
            return a < b;
        });
        return string(teams.begin(), teams.end());
    }
};
      

import java.util.*;

class Solution {
    public String rankTeams(String[] votes) {
        if (votes.length == 0) return "";
        int n = votes[0].length();
        Map<Character, int[]> count = new HashMap<>();
        for (String vote : votes) {
            for (int i = 0; i < n; ++i) {
                char team = vote.charAt(i);
                count.putIfAbsent(team, new int[n]);
                count.get(team)[i]++;
            }
        }
        List<Character> teams = new ArrayList<>();
        for (char c : votes[0].toCharArray()) teams.add(c);
        teams.sort((a, b) -> {
            for (int i = 0; i < n; ++i) {
                if (count.get(a)[i] != count.get(b)[i])
                    return count.get(b)[i] - count.get(a)[i];
            }
            return a - b;
        });
        StringBuilder sb = new StringBuilder();
        for (char c : teams) sb.append(c);
        return sb.toString();
    }
}
      

/**
 * @param {string[]} votes
 * @return {string}
 */
var rankTeams = function(votes) {
    if (votes.length === 0) return "";
    const n = votes[0].length;
    const count = {};
    for (const vote of votes) {
        for (let i = 0; i < n; ++i) {
            const team = vote[i];
            if (!count[team]) count[team] = Array(n).fill(0);
            count[team][i]++;
        }
    }
    const teams = votes[0].split('');
    teams.sort((a, b) => {
        for (let i = 0; i < n; ++i) {
            if (count[a][i] !== count[b][i])
                return count[b][i] - count[a][i];
        }
        return a.localeCompare(b);
    });
    return teams.join('');
};