Rank Teams by Votes

Ah, the classic dilemma of ranking teams based on votes! It’s like trying to decide who gets the last slice of pizza at a party—everyone has an opinion, and somehow, it always ends in chaos. Imagine a group of friends voting on which movie to watch. One friend wants a horror flick, another is all about rom-coms, and the third just wants to watch cat videos. In the end, you’re left with a mishmash of preferences that somehow needs to be sorted out. Welcome to the world of “Rank Teams by Votes”!

Problem Description

In this problem, you are given a list of votes, where each vote is a string representing the ranking of teams. Your task is to rank the teams based on these votes. The team with the highest rank in the most votes should come first, and in case of a tie, the team with the lexicographically smaller name should be ranked higher. It’s like a popularity contest, but with a twist—because who doesn’t love a good twist?

Solution in Java


class Team {
  public char name;
  public int[] rank;
  public Team(char name, int teamSize) {
    this.name = name;
    this.rank = new int[teamSize];
  }
}

class Solution {
  public String rankTeams(String[] votes) {
    final int teamSize = votes[0].length();
    StringBuilder sb = new StringBuilder();
    Team[] teams = new Team[26];

    for (int i = 0; i < 26; ++i)
      teams[i] = new Team((char) ('A' + i), teamSize);

    for (final String vote : votes)
      for (int i = 0; i < teamSize; ++i)
        ++teams[vote.charAt(i) - 'A'].rank[i];

    Arrays.sort(teams, new Comparator() {
      @Override
      public int compare(Team a, Team b) {
        for (int i = 0; i < a.rank.length; ++i)
          if (a.rank[i] > b.rank[i])
            return -1;
          else if (a.rank[i] < b.rank[i])
            return 1;
        return a.name - b.name;
      }
    });

    for (int i = 0; i < teamSize; ++i)
      sb.append(teams[i].name);

    return sb.toString();
  }
}

Approach

The approach taken in this solution is straightforward yet effective. We first create a Team class to hold the name and ranking of each team. We then initialize an array of Team objects for all possible teams (A-Z). For each vote, we update the rank of each team based on its position in the vote. Finally, we sort the teams based on their ranks and names, and construct the final ranking string.

Time and Space Complexity

Time Complexity: O(N * M + K log K), where N is the number of votes, M is the number of teams (which is constant at 26), and K is the number of teams being sorted.

Space Complexity: O(K), where K is the number of teams (again, constant at 26).

Real-World Example

Imagine a school where students are voting for their favorite sports teams. Each student submits their top three teams, and the school wants to announce the most popular team. Using the same logic as our code, the school can tally the votes and declare the winning team based on the highest ranks. It’s a fun way to engage students and maybe even spark a little friendly rivalry!