Rank Teams by Votes
Problem Description:
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 system. Sort all teams according to the ranking system described above.
Return a string of all teams sorted by the ranking system.
Examples:
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.
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.
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.
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We are given votes or rankings provided by voters for some teams. The team names are represented by capital English letters, so there can be at most 26 teams. Based on these rankings, we need to determine the overall ranking of the teams, considering how well they collectively performed across all positions.
To decide the rankings, we first look at which team received the most votes for the first position. If two or more teams tie for the first position, we compare the number of votes they received for the second position. If they tie again, we continue this process for subsequent positions. If even after considering all positions two teams are still tied, we rank them alphabetically based on their team name, with the team that comes earlier in the alphabet being placed first.
To solve this, let’s find out how many votes each team gets for every position from 1 to the total number of teams. For example, we count how many first-place votes a team like "X" receives, then how many second-place votes, and so on. Once we have this information for all teams, we can compare each pair of teams.
For every pair of teams, we start by comparing their votes for the first position. The team with more votes in the first position will rank higher. If they have the same number of votes for the first position, we compare their votes for the second position, and so on, until we find a difference. If all positions have the same number of votes, we use alphabetical order to decide the ranking, placing the team that comes earlier in the alphabet first.
By following this method, we can sort all the teams according to the required conditions.
How to do it?
As discussed above, to solve this, we need to track how many votes each team gets in a certain position so we can compare them.
To do this efficiently, we can use a hashtable or a 2D array. The 2D array would represent teams vs. positions, where the rows correspond to teams, and the columns represent positions. Since there can be n voters and m teams, the array will be of size n × m. Using this, we can store how many votes each team has received at a specific position.
Once we have this data, we need to sort the teams based on the given conditions. For this, we can use any sorting algorithm, such as bubble sort. In the sorting process, we compare two teams by checking their votes starting from position 1. The team with more votes in this position will rank higher. If both teams have the same number of votes at position 1, we move to position 2, and so on, until we find a difference. If the votes are the same for all positions, we sort them alphabetically. This ensures the teams are ranked according to the specified rules.
Finally, after sorting the teams based on the given conditions, we combine them into a single string in the sorted order and return the result as the final ranked string.
Let's understand with an example:
Input: votes = ["ABC", "ACB", "ABC", "ACB", "ACB"]
Step 1: Count Votes
For each team (A, B, C), we count how many times they are placed at each position:
Team A: 5 votes for Position 1, 0 votes for Position 2, 0 votes for Position 3
Team B: 0 votes for Position 1, 2 votes for Position 2, 3 votes for Position 3
Team C: 0 votes for Position 1, 3 votes for Position 2, 2 votes for Position 3
Step 2: Sort Teams
We compare teams using the following rules:
Compare votes for Position 1: Team A has the most votes, so A ranks first.
Compare votes for Position 2: Team C has more votes (3) than B (2), so C ranks second, and B is third.
No further comparisons are needed, as the teams are distinct after this step.
Step 3: Return the Sorted String
The final sorted order of the teams is: "ACB".
This is the ranked string we return.
How to code it up:
Here are the concise steps to code the solution:
- Initialize the Result List:
Set the result list to the order of teams from the first vote. This will be the list that gets sorted. - Create a Data Structure to Track Rankings:
Create a 2D array or matrix where each row represents a team and each column represents a ranking position (1st, 2nd, etc.). Initialize it to store the number of votes a team received at each position. - Populate the Ranking Data:
Iterate through all the votes. For each vote, update the matrix by incrementing the corresponding position for each team in the vote. - Sort the Teams Based on Rankings:
Use sorting logic where each team is compared against others in terms of their votes at each ranking position. Start from position 1 and compare the teams based on the number of votes each received at that position.
If the votes are the same for a given position, move on to the next position until a difference is found.
If all positions are the same (i.e., teams are tied), sort them alphabetically by team name. - Swap Teams if Needed:
If one team should be ranked higher than another based on the comparison, swap their positions in the result list. - Return the Final Sorted List:
After all teams have been compared and ordered, return the final list of teams sorted according to the ranking criteria.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
// Function to rank teams based on votes
string rankTeams(vector<string>& votes) {
// Initialize the answer string to the first vote (as the initial order)
string ans = votes[0];
// Create a 2D array to track the votes for each team at each position
vector<vector<int>> rank(26, vector<int>(26, 0));
// Populate the rank table with the rankings from all votes
for (auto &vote : votes) {
// For each vote, count the votes at each position for each team
for (int i = 0; i < vote.length(); i++) {
// Increment the count for the team at position i
rank[vote[i] - 'A'][i]++;
}
}
// Manual sorting using nested loops to compare teams
for (int i = 0; i < ans.size(); i++) {
for (int j = i + 1; j < ans.size(); j++) {
char a = ans[i], b = ans[j];
// Flag to track if a swap is needed
bool shouldSwap = false;
// Compare rankings for each position, starting from the first position
for (int k = 0; k < votes[0].size(); k++) {
// If 'a' has more votes at position k, no swap is needed
if (rank[a - 'A'][k] > rank[b - 'A'][k]) {
// 'a' is ranked higher; no need to swap
break;
}
// If 'b' has more votes at position k, swap is needed
if (rank[a - 'A'][k] < rank[b - 'A'][k]) {
// 'b' is ranked higher; we need to swap
shouldSwap = true;
break;
}
}
// If the votes are the same at all positions, sort alphabetically
if (!shouldSwap && rank[a - 'A'] == rank[b - 'A'] && a > b) {
// Alphabetical order if all positions are equal
shouldSwap = true;
}
// Perform the swap if necessary
if (shouldSwap) {
swap(ans[i], ans[j]);
}
}
}
// Return the sorted result string
return ans;
}
};
2. Java Try on Compiler
import java.util.*;
public class Solution {
public String rankTeams(String[] votes) {
// Initialize the answer string to the first vote (as the initial order)
String ans = votes[0];
// Create a 2D array to track the votes for each team at each position
int[][] rank = new int[26][votes[0].length()];
// Populate the rank table with the rankings from all votes
for (String vote : votes) {
for (int i = 0; i < vote.length(); i++) {
rank[vote.charAt(i) - 'A'][i]++;
}
}
// Manual sorting using nested loops to compare teams
for (int i = 0; i < ans.length(); i++) {
for (int j = i + 1; j < ans.length(); j++) {
char a = ans.charAt(i);
char b = ans.charAt(j);
// Flag to track if a swap is needed
boolean shouldSwap = false;
// Compare rankings for each position, starting from the first position
for (int k = 0; k < votes[0].length(); k++) {
if (rank[a - 'A'][k] > rank[b - 'A'][k]) {
break; // 'a' is ranked higher; no need to swap
}
if (rank[a - 'A'][k] < rank[b - 'A'][k]) {
shouldSwap = true; // 'b' is ranked higher; we need to swap
break;
}
}
// If the votes are the same at all positions, sort alphabetically
if (!shouldSwap && Arrays.equals(rank[a - 'A'], rank[b - 'A']) && a > b) {
shouldSwap = true; // Alphabetical order if all positions are equal
}
// Perform the swap if necessary
if (shouldSwap) {
ans = swap(ans, i, j);
}
}
}
// Return the sorted result string
return ans;
}
// Helper function to swap characters at two positions in the string
private String swap(String str, int i, int j) {
char[] arr = str.toCharArray();
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return new String(arr);
}
}
3. Python Try on Compiler
class Solution:
def rankTeams(self, votes):
# Initialize the answer string to the first vote (as the initial order)
ans = votes[0]
# Create a 2D array to track the votes for each team at each position
rank = [[0] * len(votes[0]) for _ in range(26)]
# Populate the rank table with the rankings from all votes
for vote in votes:
for i, team in enumerate(vote):
rank[ord(team) - ord('A')][i] += 1
# Manual sorting using nested loops to compare teams
# Convert string to list for swapping
ans = list(ans)
for i in range(len(ans)):
for j in range(i + 1, len(ans)):
a, b = ans[i], ans[j]
# Flag to track if a swap is needed
shouldSwap = False
# Compare rankings for each position, starting from the first position
for k in range(len(votes[0])):
if rank[ord(a) - ord('A')][k] > rank[ord(b) - ord('A')][k]:
# 'a' is ranked higher; no need to swap
break
if rank[ord(a) - ord('A')][k] < rank[ord(b) - ord('A')][k]:
# 'b' is ranked higher; we need to swap
shouldSwap = True
break
# If the votes are the same at all positions, sort alphabetically
if not shouldSwap and rank[ord(a) - ord('A')] == rank[ord(b) - ord('A')] and a > b:
shouldSwap = True
# Perform the swap if necessary
if shouldSwap:
ans[i], ans[j] = ans[j], ans[i]
# Return the sorted result string
return ''.join(ans)
4. Javascript Try on Compiler
var rankTeams = function(votes) {
// Initialize the answer string to the first vote (as the initial order)
let ans = votes[0];
// Create a 2D array to track the votes for each team at each position
const rank = Array.from({ length: 26 }, () => Array(votes[0].length).fill(0));
// Populate the rank table with the rankings from all votes
for (let vote of votes) {
for (let i = 0; i < vote.length; i++) {
rank[vote.charCodeAt(i) - 65][i]++;
}
}
// Manual sorting using nested loops to compare teams
// Convert string to array for swapping
ans = [...ans];
for (let i = 0; i < ans.length; i++) {
for (let j = i + 1; j < ans.length; j++) {
const a = ans[i], b = ans[j];
let shouldSwap = false;
// Compare rankings for each position, starting from the first position
for (let k = 0; k < votes[0].length; k++) {
if (rank[a.charCodeAt(0) - 65][k] > rank[b.charCodeAt(0) - 65][k]) {
// 'a' is ranked higher; no need to swap
break;
}
if (rank[a.charCodeAt(0) - 65][k] < rank[b.charCodeAt(0) - 65][k]) {
// 'b' is ranked higher; we need to swap
shouldSwap = true;
break;
}
}
// If the votes are the same at all positions, sort alphabetically
if (!shouldSwap && rank[a.charCodeAt(0) - 65].every((val, index) => val === rank[b.charCodeAt(0) - 65][index]) && a > b) {
shouldSwap = true;
}
// Perform the swap if necessary
if (shouldSwap) {
[ans[i], ans[j]] = [ans[j], ans[i]];
}
}
}
// Return the sorted result string
return ans.join('');
};
Time Complexity: O(n * m + m³)
The time complexity of this approach can be broken down into the following steps:
- Populating the rank table:
For each vote in votes, we iterate over each team in the vote.
Suppose there are n votes and m teams (the length of the vote string).
We iterate over all n votes and for each vote, we loop over m teams.
The time complexity for this step is O(n * m). - Sorting teams manually using nested loops:
In the worst case, the sorting involves two nested loops over the teams.
The outer loop runs m times (since there are m teams), and the inner loop also runs m times (because we compare each team with every other team).
Inside the inner loop, we compare the ranking of two teams across all positions, which takes m iterations (because the ranking table has m positions).
The swap operation itself takes O(m) time (to convert the string to a character array and swap two characters).
Thus, the time complexity of the sorting step is O(m² * m) = O(m³) because for each team pair, we compare the rankings across all positions, which involves O(m) comparisons.
Overall Time Complexity:
- The time complexity for populating the rank table is O(n * m).
- The time complexity for sorting is O(m³).
- Therefore, the overall time complexity of the code is: O(n * m + m³).
Space Complexity: O(n * m)
Auxiliary Space Complexity: O(m )
Explanation: We maintain a 2D array of size 26x26 (rank[26][26]) to store the vote counts for each team in each position. Although this array is fixed and doesn't grow with the input size, it consumes O(1) space since it is a constant size. Specifically, it is a constant size because the number of teams (m) is capped at 26 (as there are 26 uppercase English letters representing the teams). Hence, the auxiliary space for this structure is O(1).
We use ans to store the team names in their original order and then sort them. This requires O(m) space for storing the teams during sorting.Other variables such as the loop counters and temporary variables (like shouldSwap, a, b) use O(1) space.
Thus, the total auxiliary space is: O(m).
Total Space Complexity: O(n)
Explanation: The input is the votes array, which has n votes, and each vote is a string of length m. Thus, the space for the input is O(n * m).
Therefore, the total space used by the algorithm is O(n * m).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n * m), which is efficient given the problem constraints.
Since the time complexity is O(n * m), it involves iterating over each vote and each team within each vote. For n = 1000 and m = 26, the solution will execute O(1000 * 26) = O(26,000) operations. This is well within typical time limits for competitive programming, where up to 10⁶ operations per test case are usually allowed.
Since O(n * m) results in a maximum of 26,000 operations (for n = 1000 and m = 26), the solution will execute efficiently within time limits for large inputs.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10⁶ operations. However, for n ≤ 1000 and m ≤ 26, the solution will not face Time Limit Exceeded (TLE) errors.
Thus, the solution meets the time limits for all test cases and is efficient enough to handle the given constraints without causing performance issues.
Can we optimize it?
In our previous approach, we precomputed the position-wise votes for each team and sorted the teams based on these votes using bubble sort. This led to a time complexity of O(n * m + m³).
So, how can we optimize this? The answer is simple: instead of bubble sort, we can use more efficient sorting algorithms like merge sort or heap sort, which reduce the time complexity to O(n log n). But using these algorithms might make the code lengthy and more complex to implement. Is there a more concise and efficient option?
Yes, we can use the inbuilt sort() function! This function is widely available in many programming languages and allows us to sort collections (like arrays, lists, or vectors) in ascending order by default. Furthermore, it provides the ability to define a custom comparator, which makes it versatile and perfect for our use case. The custom comparator lets us define our sorting logic, making the code both concise and efficient.
Instead of manually comparing each team's ranking for all positions, we can compare each team’s position-wise votes using a more efficient sorting mechanism. Each team will be represented by a vector of votes for each position (first place, second place, etc.). When comparing two teams, we simply compare their position-wise vote vectors.
The comparison will work as follows: we start from the first position (most important position), and whichever team has more votes in this position will be placed higher. If the votes for the first position are the same for both teams, we move to the second position and compare again, continuing in this manner until we find a difference. If two teams have the same votes for all positions, we will return the team that is alphabetically first.
Understand with an example:
Let's take an example with two teams: Team A and Team B. Assume there are 3 positions, so each team has a position vector representing how many votes they received for each position.
Team A's position vector:
- [3, 2, 1]
- Team A received 3 votes for 1st position, 2 votes for 2nd position, and 1 vote for 3rd position.
Team B's position vector:
- [3, 3, 1]
- Team B received 3 votes for 1st position, 3 votes for 2nd position, and 1 vote for 3rd position.
Now, when sorting these two teams:
- First position comparison:
- Both Team A and Team B received 3 votes for the 1st position, so there is no difference at this step. We move to the next position.
- Second position comparison:
- Team A received 2 votes for the 2nd position, while Team B received 3 votes.
- Since Team B has more votes in the second position, Team B is ranked higher.
Thus, Team B will come before Team A in the sorted order, even though both teams received the same votes for the 1st position. If the second positions were also tied, we would move on to the third position for comparison.
This is how position vectors are compared: from left to right, prioritizing the earlier positions, and resolving ties as we go along.
We can compare the position-wise vote vectors of two teams by using the comparison operators >, <, and ==. These operators will help us check which team has a higher rank in each position. If one team has more votes in a higher position (e.g., first place), it will be ranked higher. If both teams have the same votes across all positions, we will compare them alphabetically.
This approach leverages inbuilt sorting which is optimized and significantly faster than manual sorting. By directly comparing the vote vectors, we ensure the teams are sorted efficiently based on their overall ranking, and the use of alphabetical sorting as a tiebreaker ensures the correct order when necessary. This makes the solution much more efficient, both in terms of readability and time complexity, compared to the previous approach.
Let us understand this with the help of a video,
Let's understand with an example:
Input: votes = ["ABC", "ACB", "ABC", "ACB", "ACB"]
Step 1: Count Votes
For each team (A, B, C), we count how many times they are placed at each position:
Team A: 5 votes for Position 1, 0 votes for Position 2, 0 votes for Position 3
Team B: 0 votes for Position 1, 2 votes for Position 2, 3 votes for Position 3
Team C: 0 votes for Position 1, 3 votes for Position 2, 2 votes for Position 3
Step 2: Sorting Teams
Teams to sort: The teams in the original order from the first vote are ["A", "B", "C"].
Sorting Logic:
We compare the teams' position-wise vote vectors:
Compare A and B:
- A's position-wise vote vector: [5, 0, 0]
- B's position-wise vote vector: [0, 2, 3]
- First position: A has 5 votes, and B has 0 votes. So, A is ranked higher than B. No need to swap.
Compare A and C:
- A's position-wise vote vector: [5, 0, 0]
- C's position-wise vote vector: [0, 3, 2]
- First position: A has 5 votes, and C has 0 votes. So, A is ranked higher than C. No need to swap.
Compare B and C:
- B's position-wise vote vector: [0, 2, 3]
- C's position-wise vote vector: [0, 3, 2]
- First position: Both B and C have 0 votes in the first position.
- Second position: B has 2 votes, and C has 3 votes. C is ranked higher than B, so B and C need to be swapped.
Step 3: Result
After sorting, the final order of teams is "ACB".
Thus, the output is "ACB".
How to code it up?
Here are concise and generic steps to code the solution:
Define the Input:
- Take the list of votes as input. Each vote is a string representing the ranking of teams.
Initialize the Rank Table:
- Create a 2D array (or table) to store the number of votes each team has at each position in the ranking.
- Use a fixed-size array (26 x 26, for the 26 English uppercase letters) to track votes for all positions.
Populate the Rank Table:
- Loop over all the votes.
- For each vote, loop through each team in the vote string and update the rank table by incrementing the vote count for the corresponding position.
Sort the Teams:
- Define a sorting function that compares two teams based on their position-wise votes.
- First, compare the votes for each team at each position (starting from the first).
- If one team has more votes at a certain position, it should be ranked higher.
- If both teams have the same votes at all positions, compare them alphabetically (lexicographically).
Return the Sorted Result:
- After sorting the teams based on the rank table and comparison criteria, return the sorted string of team names.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
// Function to rank teams based on votes
string rankTeams(vector<string>& votes) {
// Initialize the answer string to the first vote (as the initial order)
string ans = votes[0];
// Create a 2D array to track the votes for each team at each position
vector<vector<int>> rank(26, vector<int>(26, 0));
// Populate the rank table with the rankings from all votes
for(auto &vote: votes) {
// For each vote, count the votes at each position for each team
for(int i = 0; i < vote.length(); i++) {
// Increment the count for the team at position i
rank[vote[i] - 'A'][i]++;
}
}
// Sort the teams based on their position-wise vote vectors and alphabetical order
sort(ans.begin(), ans.end(), [&](const char &a, const char &b) {
// If both teams have the same vote vector, compare alphabetically
if(rank[a - 'A'] == rank[b - 'A'])
return a < b;
// Otherwise, sort based on the rank (more votes at earlier positions)
return rank[a - 'A'] > rank[b - 'A'];
});
// Return the sorted result string
return ans;
}
};
2. Java Try on Compiler
import java.util.*;
class Solution {
public String rankTeams(String[] votes) {
// Initialize the answer string to the first vote (as the initial order)
String ans = votes[0];
// Create a 2D array to track the votes for each team at each position
int[][] rank = new int[26][votes[0].length()];
// Populate the rank table with the rankings from all votes
for (String vote : votes) {
for (int i = 0; i < vote.length(); i++) {
rank[vote.charAt(i) - 'A'][i]++;
}
}
// Convert the result string to a Character array for sorting
Character[] result = new Character[ans.length()];
for (int i = 0; i < ans.length(); i++) {
result[i] = ans.charAt(i);
}
// Sort the teams based on their position-wise vote vectors and alphabetical order
Arrays.sort(result, new Comparator<Character>() {
@Override
public int compare(Character a, Character b) {
// Compare rank position vectors for both teams
for (int i = 0; i < votes[0].length(); i++) {
if (rank[a - 'A'][i] != rank[b - 'A'][i]) {
// More votes should come first
return rank[b - 'A'][i] - rank[a - 'A'][i];
}
}
// If position vectors are the same, compare alphabetically
return a - b; // Alphabetical order if vote vectors are equal
}
});
// Return the sorted result string
StringBuilder sortedResult = new StringBuilder();
for (Character c : result) {
sortedResult.append(c);
}
return sortedResult.toString();
}
}
3. Python Try on Compiler
class Solution:
def rankTeams(self, votes):
# Initialize the answer string to the first vote (as the initial order)
ans = list(votes[0])
# Create a 2D array to track the votes for each team at each position
rank = [[0] * len(votes[0]) for _ in range(26)]
# Populate the rank table with the rankings from all votes
for vote in votes:
for i, team in enumerate(vote):
rank[ord(team) - ord('A')][i] += 1
# Sort the teams based on their position-wise vote vectors and alphabetical order
ans.sort(key=lambda x: tuple((-rank[ord(x) - ord('A')][i] for i in range(len(votes[0])))) + (x,))
# Return the sorted result string
return ''.join(ans)
4. Javascript Try on Compiler
var rankTeams = function(votes) {
// Initialize the answer string to the first vote (as the initial order)
let ans = votes[0];
// Create a 2D array to track the votes for each team at each position
let rank = Array.from({ length: 26 }, () => Array(votes[0].length).fill(0));
// Populate the rank table with the rankings from all votes
for (let vote of votes) {
for (let i = 0; i < vote.length; i++) {
rank[vote.charCodeAt(i) - 'A'.charCodeAt(0)][i]++;
}
}
// Sort the teams based on their position-wise vote vectors and alphabetical order
ans = [...ans].sort((a, b) => {
for (let i = 0; i < votes[0].length; i++) {
if (rank[a.charCodeAt(0) - 'A'.charCodeAt(0)][i] !== rank[b.charCodeAt(0) - 'A'.charCodeAt(0)][i]) {
return rank[b.charCodeAt(0) - 'A'.charCodeAt(0)][i] - rank[a.charCodeAt(0) - 'A'.charCodeAt(0)][i]; // More votes should come first
}
}
return a.localeCompare(b); // Alphabetical order if vote vectors are equal
});
// Return the sorted result string
return ans.join('');
};
Time Complexity: O(n * m + m² * log m)
Let's break down the time complexity for each part of the code:
- Populating the Rank Table
You iterate over all votes and for each vote, you process each team's rank in every position. Outer loop: Processes n votes (where n is the number of votes). Inner loop: Processes m teams (where m is the number of teams per vote). Time complexity for this step: O(n * m). - Sorting the Teams
You sort the list of teams based on their rank vectors. Sorting uses a comparison-based algorithm (e.g., Timsort, MergeSort). Sorting complexity: The sorting algorithm has a worst-case time complexity of O(m * log m), where m is the number of teams. Comparison complexity: Each comparison involves checking the rank vectors of the two teams. Each comparison requires O(m) operations because we check m positions in the rank vector. Total sorting complexity: O(m² * log m) because for each pair of teams, the comparison takes O(m) time and there are O(m * log m) comparisons in total. - Rebuilding the Sorted Result
After sorting, you rebuild the result by iterating over the sorted list of teams, which takes O(m) time to construct the final sorted string.
Total Time Complexity
Combining the time complexities of each step:
Populating the rank table: O(n * m) Sorting the teams: O(m² * log m) Rebuilding the result string: O(m) Thus, the total time complexity is: O(n * m + m² * log m)
Space Complexity: O(n * m)
Auxiliary Space Complexity: O(m)
Explanation: We maintain a 2D array of size 26x26 (rank[26][26]) to store the vote counts for each team in each position. Although this array is fixed and doesn't grow with the input size, it consumes O(1) space since it is a constant size. Specifically, it is a constant size because the number of teams (m) is capped at 26 (as there are 26 uppercase English letters representing the teams). Hence, the auxiliary space for this structure is O(1).
We use ans to store the team names in their original order and then sort them. This requires O(m) space for storing the teams during sorting.
Total Space Complexity: O(n * m)
Explanation: The input votes list (votes) contains n strings of length m. The space required for storing this list is O(n * m), as each string is of length m and there are n votes.
The total space complexity is O(n * m).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.Since the result may be very large, so you need to return a string instead of an integer.
You are given a 0-indexed integer array mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system.
The mapped value of an integer is the new integer obtained by replacing each occurrence of digit i in the integer with mapping[i] for all 0 <= i <= 9.
You are also given another integer array nums.
Return the array nums sorted in non-decreasing order based on the mapped values of its elements.
Notes:
1. Elements with the same mapped values should appear in the same relative order as in the input.
2. The elements of nums should only be sorted based on their mapped values and not be replaced by them.