# Rank Teams by Votes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rank-teams-by-votes)
Canonical: https://scaleengineer.com/dsa/problems/rank-teams-by-votes
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Flipkart](https://scaleengineer.com/companies/flipkart), [eBay](https://scaleengineer.com/companies/ebay), [Coursera](https://scaleengineer.com/companies/coursera)
---
## Problem
In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

You are given an array of strings `votes` which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return _a string of all teams **sorted** by the ranking system_.

**Example 1:**

**Input:** votes = ["ABC","ACB","ABC","ACB","ACB"]
**Output:** "ACB"
**Explanation:** 
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.

**Example 2:**

**Input:** votes = ["WXYZ","XYZW"]
**Output:** "XWYZ"
**Explanation:**
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position. 

**Example 3:**

**Input:** votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
**Output:** "ZMNAGUEDSJYLBOPHRQICWFXTVK"
**Explanation:** Only one voter, so their votes are used for the ranking.

**Constraints:**

* `1 <= votes.length <= 1000`
* `1 <= votes[i].length <= 26`
* `votes[i].length == votes[j].length` for `0 <= i, j < votes.length`.
* `votes[i][j]` is an English **uppercase** letter.
* All characters of `votes[i]` are unique.
* All the characters that occur in `votes[0]` **also occur** in `votes[j]` where `1 <= j < votes.length`.

# Approaches
## Brute-Force with List of Custom Objects
This approach involves creating a custom class to store statistics for each team (name and vote counts for each rank). We use a list of these objects. To count votes, we iterate through all votes and for each ranked team, we linearly search the list to find the corresponding team object and update its counts. Finally, we sort this list using a custom comparator based on the ranking rules.
**Time:** O(N * M^2), where `N` is the number of voters and `M` is the number of teams. The vote counting involves three nested loops: iterating through `N` votes, `M` ranks, and a linear search of `M` teams, giving `O(N * M * M)`. The sorting takes `O(M^2 * log M)`. The total complexity is dominated by the counting phase. · **Space:** O(M^2), where `M` is the number of teams. We store a list of `M` `TeamStats` objects, and each object contains an integer array of size `M`.
**Pros:** The approach is conceptually straightforward, using a list of custom objects to model the problem's data, which can be easy to understand and implement.
**Cons:** The primary drawback is the inefficiency of the vote counting step. Using a linear search (`O(M)`) within nested loops to find and update team statistics results in a high time complexity, making it unsuitable for larger numbers of teams.
### Explanation
We first define a helper class, say `TeamStats`, which holds the team's character (`char name`) and an integer array (`int[] votes`) to store the number of votes it received for each rank.

We initialize a `List<TeamStats>` by iterating through the first vote string `votes[0]`. For each character (team), we create a new `TeamStats` object and add it to the list.

The main part is counting the votes. We loop through each `vote` string in the input `votes` array. For each position `j` in a `vote`, we identify the team `c = vote.charAt(j)`. We then perform a linear search through our `teamStatsList` to find the `TeamStats` object for team `c`. This search takes time proportional to the number of teams. Once found, we increment `votes[j]`.

After counting all votes, we sort the `teamStatsList`. The sorting logic is encapsulated in a custom `Comparator`. This comparator compares two `TeamStats` objects by iterating through their `votes` arrays from rank 1 to the last rank. The first rank where the vote counts differ determines the order. If all vote counts are identical, the teams are sorted alphabetically by their `name`.

Finally, we construct the result string by appending the `name` of each `TeamStats` object from the sorted list.

```java
class Solution {
    class TeamStats {
        char name;
        int[] votes;
        TeamStats(char name, int numTeams) {
            this.name = name;
            this.votes = new int[numTeams];
        }
    }

    public String rankTeams(String[] votes) {
        if (votes == null || votes.length == 0) {
            return "";
        }
        int numTeams = votes[0].length();
        List<TeamStats> teamStatsList = new ArrayList<>();
        for (char teamName : votes[0].toCharArray()) {
            teamStatsList.add(new TeamStats(teamName, numTeams));
        }

        for (String vote : votes) {
            for (int i = 0; i < numTeams; i++) {
                char teamName = vote.charAt(i);
                // Linear search to find the team
                for (TeamStats stats : teamStatsList) {
                    if (stats.name == teamName) {
                        stats.votes[i]++;
                        break;
                    }
                }
            }
        }

        Collections.sort(teamStatsList, (a, b) -> {
            for (int i = 0; i < numTeams; i++) {
                if (a.votes[i] != b.votes[i]) {
                    return b.votes[i] - a.votes[i];
                }
            }
            return a.name - b.name;
        });

        StringBuilder result = new StringBuilder();
        for (TeamStats stats : teamStatsList) {
            result.append(stats.name);
        }
        return result.toString();
    }
}
```
### Algorithm
- Define a custom class, `TeamStats`, to hold a team's character name and an integer array for its vote counts across all ranks.
- Determine the number of teams, `M`, from the length of the first vote string.
- Create a `List<TeamStats>` and initialize it by creating a `TeamStats` object for each team found in `votes[0]`.
- Iterate through each `vote` string in the input `votes` array.
- For each character `c` at rank `j` in the current `vote`, perform a linear search through the `teamStatsList` to find the `TeamStats` object corresponding to team `c`.
- Once found, increment the vote count for that team at rank `j` (i.e., `stats.votes[j]++`).
- After processing all votes, sort the `teamStatsList` using a custom `Comparator`.
- The comparator logic is as follows: for two teams, iterate through their vote count arrays from rank 0 to `M-1`. The first rank with a differing vote count determines the order (higher votes first). If all vote counts are identical, sort the teams alphabetically by name.
- Construct the final ranked string by appending the names of the teams from the sorted list.

## HashMap for Efficient Counting and Custom Sort
This is a more optimized approach. We use a HashMap to store the vote counts for each team. The team character is the key, and an integer array representing its vote counts for each rank is the value. This allows for `O(1)` average time access to a team's stats. After counting all votes, we extract the teams, sort them using a custom comparator, and build the result string.
**Time:** O(N * M + M^2 * log M), where `N` is the number of voters and `M` is the number of teams. Counting votes takes `O(N * M)`. Sorting `M` teams requires `O(M log M)` comparisons, where each comparison can take up to `O(M)` time, resulting in a sorting time of `O(M^2 * log M)`. Since `M <= 26`, the complexity is effectively linear in the input size, `O(N * M)`. · **Space:** O(M^2), where `M` is the number of teams. The HashMap stores `M` keys, and each key is associated with an integer array of size `M`. An additional `O(M)` space is used for the list of teams during sorting.
**Pros:** Highly efficient vote counting with `O(1)` average time complexity for map operations.; This is a clean, standard, and robust solution for this type of counting and sorting problem.; It's very efficient given the problem constraints, likely the intended solution.
**Cons:** The space complexity is `O(M^2)`, which is quadratic in the number of teams. However, given the constraint that `M <= 26`, this is a very small and acceptable amount of space.
### Explanation
The core idea is to replace the inefficient linear search of the previous approach with a highly efficient HashMap lookup. We create a `Map<Character, int[]>`, where the key is the team's character and the value is an integer array of size `M` (number of teams) to store vote counts.

First, we populate the map with all the teams from `votes[0]`, initializing their vote count arrays with zeros.

Next, we process the votes. We iterate through each `vote` string. For each character `c` at position `j`, we retrieve its corresponding integer array from the map in `O(1)` average time and increment the count at index `j`, i.e., `map.get(c)[j]++`. This counting process is much faster.

Once all votes are tallied, we need to sort the teams. We get a list of all team characters from the map's key set.

We then sort this list using `Collections.sort()` with a custom `Comparator`. The comparator logic is identical to the previous approach: it fetches the vote arrays for two teams from the map and compares them rank by rank. If all ranks are tied, it falls back to alphabetical sorting of the team characters.

Finally, the sorted list of characters is joined to form the final ranked string.

```java
class Solution {
    public String rankTeams(String[] votes) {
        if (votes == null || votes.length == 0) {
            return "";
        }
        int numTeams = votes[0].length();
        Map<Character, int[]> map = new HashMap<>();

        // Initialize map for all teams
        for (char teamName : votes[0].toCharArray()) {
            map.put(teamName, new int[numTeams]);
        }

        // Tally votes
        for (String vote : votes) {
            for (int i = 0; i < numTeams; i++) {
                char teamName = vote.charAt(i);
                map.get(teamName)[i]++;
            }
        }

        // Get list of teams to sort
        List<Character> teams = new ArrayList<>(map.keySet());

        // Sort teams using custom comparator
        Collections.sort(teams, (a, b) -> {
            int[] votesA = map.get(a);
            int[] votesB = map.get(b);
            for (int i = 0; i < numTeams; i++) {
                if (votesA[i] != votesB[i]) {
                    return votesB[i] - votesA[i]; // Descending order of votes
                }
            }
            return a - b; // Alphabetical order for ties
        });

        // Build result string
        StringBuilder result = new StringBuilder();
        for (char team : teams) {
            result.append(team);
        }
        return result.toString();
    }
}
```
### Algorithm
- Determine the number of teams, `M`, from `votes[0].length()`.
- Create a `Map<Character, int[]>` to store vote counts. The key is the team character, and the value is an integer array of size `M`.
- Initialize the map by iterating through `votes[0]`. For each team character, add an entry to the map with a new integer array of size `M` initialized to zeros.
- Iterate through each `vote` string in the `votes` array. For each character `c` at rank `j`, retrieve its count array from the map (an `O(1)` operation on average) and increment the count at index `j`.
- After counting, create a `List<Character>` from the map's key set.
- Sort this list using a custom `Comparator`.
- The comparator fetches the vote count arrays for two teams from the map and compares them rank by rank. If votes for a rank differ, it sorts by the higher vote count. If all ranks are tied, it sorts alphabetically.
- Build the final result string by concatenating the characters from the sorted list.

# Solutions
### Java

```java
class Solution {
public
  String rankTeams(String[] votes) {
    int n = votes[0].length();
    int[][] cnt = new int[26][n];
    for (var vote : votes) {
      for (int i = 0; i < n; ++i) {
        cnt[vote.charAt(i) - 'A'][i]++;
      }
    }
    Character[] cs = new Character[n];
    for (int i = 0; i < n; ++i) {
      cs[i] = votes[0].charAt(i);
    }
    Arrays.sort(
        cs, (a, b)->{
          int i = a - 'A', j = b - 'A';
          for (int k = 0; k < n; ++k) {
            int d = cnt[i][k] - cnt[j][k];
            if (d != 0) {
              return d > 0 ? -1 : 1;
            }
          }
          return a - b;
        });
    StringBuilder ans = new StringBuilder();
    for (char c : cs) {
      ans.append(c);
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string rankTeams(vector<string> &votes) {
    int n = votes[0].size();
    int cnt[26][n];
    memset(cnt, 0, sizeof cnt);
    for (auto &vote : votes) {
      for (int i = 0; i < n; ++i) {
        cnt[vote[i] - 'A'][i]++;
      }
    }
    string ans = votes[0];
    sort(ans.begin(), ans.end(), [&](auto &a, auto &b) {
      int i = a - 'A', j = b - 'A';
      for (int k = 0; k < n; ++k) {
        if (cnt[i][k] != cnt[j][k]) {
          return cnt[i][k] > cnt[j][k];
        }
      }
      return a < b;
    });
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rankTeams(self, votes: List[str]) -> str: n = len(votes[0]) cnt = defaultdict(lambda: [0] * n) for vote in votes: for i, c in enumerate(vote): cnt[c][i] += 1 return "" . join(sorted(votes[0], key=lambda x: (cnt[x], - ord(x)), reverse=True))

```