We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rank Teams by Votes

Number: 1483

Difficulty: Medium

Paid? No

Companies: Atlassian, Google, Microsoft, Coursera, TikTok, Flipkart, Bloomberg, eBay

Problem Description

In a special ranking system, voters rank teams from highest to lowest. The ranking is determined by counting the votes for each position: teams with the most first-place votes rank higher. For ties in first-place votes, the count of second-place votes is used, and so on. If teams remain tied after considering all positions, they are sorted alphabetically. Given an array of vote strings (each string representing a full ranking of teams), return a string of all teams sorted according to this ranking system.

Key Insights

  • Count vote occurrences per team for each ranking position.
  • Use a data structure (dictionary/hash map) to maintain counts for each position for every team.
  • Sort teams primarily based on descending vote counts for the first, second, third position, etc.
  • Use alphabetical order as the final tie-breaker.
  • The limited number of teams (at most 26) keeps the approach efficient.

Space and Time Complexity

Time Complexity: O(n * k + k log k), where n is the number of votes and k is the number of teams. Space Complexity: O(k), for storing vote counts for each team.

Solution

The solution involves:

  1. Initializing a dictionary (or equivalent) to store an array of vote counts per team.
  2. Iterating over each vote to update the counts based on the vote position.
  3. Sorting the teams based on vote counts at each position in descending order and using lexicographical order for any ties.
  4. Concatenating the sorted team names into a single string for the final output.

Code Solutions

# Python solution for "Rank Teams by Votes"

def rankTeams(votes):
    num_positions = len(votes[0])  # number of positions in each vote
    vote_counts = {}  # dictionary to store vote counts for each team
    
    # Count votes for each team for every position
    for vote in votes:
        for rank, team in enumerate(vote):
            if team not in vote_counts:
                vote_counts[team] = [0] * num_positions
            vote_counts[team][rank] += 1

    # Sort teams based on vote counts per position (descending) and lex order for ties
    sorted_teams = sorted(vote_counts.keys(), key=lambda team: ([-count for count in vote_counts[team]], team))
    
    # Return the concatenated string of sorted teams
    return "".join(sorted_teams)

# Example usage:
votes = ["ABC","ACB","ABC","ACB","ACB"]
print(rankTeams(votes))  # Expected Output: "ACB"
← Back to All Questions