LeetCode 1366 - Rank Teams by Votes

LeetCode Problem 1366

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting, Counting

Solution

Problem Understanding

The problem describes a voting based ranking system where every voter ranks all teams from best to worst. Each vote is represented as a string, where the character at index 0 is the top ranked team, the character at index 1 is the second ranked team, and so on.

The final ranking is determined lexicographically by vote counts across positions. First, we compare how many first place votes each team received. The team with more first place votes ranks higher. If two teams are tied, we compare their second place vote counts. If they are still tied, we continue comparing third place counts, fourth place counts, and so on until the tie is broken.

If all positional vote counts are identical, then the final tie breaker is alphabetical order.

The input is an array votes, where:

• Each string contains all participating teams exactly once
• Every vote has the same length
• Teams are represented by uppercase English letters
• There are at most 26 teams because only uppercase letters are used

The output should be a single string containing all teams ordered from highest rank to lowest rank.

The constraints are important because they guide the implementation strategy:

• votes.length <= 1000
• votes[i].length <= 26

Since there are at most 26 teams, we can afford to store a full positional frequency array for each team. Even an O(26^2 log 26) style solution is extremely efficient.

Several edge cases are important:

• Only one voter exists, in which case the answer is exactly that vote.
• Multiple teams may have identical vote distributions across every position.
• Teams may tie at several positions before eventually differing later.
• Complete ties must fall back to alphabetical ordering.
• The number of teams can be as small as 1.

A naive implementation can easily fail if it only compares first place votes or if it does not properly handle alphabetical tie breaking.

Approaches

Brute Force Approach

A brute force solution would repeatedly compare every pair of teams by scanning all votes and counting how many times each team appears in each position during every comparison.

For example, when comparing team A and team B, we could:

1. Count first place votes for both teams by scanning all ballots
2. If tied, count second place votes
3. Continue until the tie is resolved
4. Repeat this process for every pair during sorting

This approach is correct because it directly follows the ranking rules during every comparison.

However, it is inefficient because the same counts are recomputed many times. Sorting requires many comparisons, and each comparison scans all votes repeatedly.

Optimal Approach

The key observation is that positional vote counts never change. Instead of recomputing them repeatedly, we can preprocess all vote statistics once.

For every team, we store:

• Number of first place votes
• Number of second place votes
• Number of third place votes
• And so on

Then we sort teams using these precomputed statistics.

For example:

Team	1st	2nd	3rd
A	5	0	0
B	0	2	3
C	0	3	2

Now sorting becomes straightforward:

• Compare first place counts
• If tied, compare second place counts
• Continue through all positions
• Finally compare alphabetically

This works efficiently because there are at most 26 teams.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(V × T² × log T × T)	O(1)	Recomputes vote counts repeatedly during sorting
Optimal	O(V × T + T log T)	O(T²)	Precomputes positional frequencies once

Where:

• V = number of votes
• T = number of teams

Since T <= 26, the optimal approach is extremely fast.

Algorithm Walkthrough

1. Determine the number of teams from the first vote.

Every vote contains all teams, so len(votes[0]) gives the total number of participating teams. 2. Create a frequency table for each team.

We use a hash map where:

• Key = team character
• Value = array of positional counts

Example:

{
    'A': [5, 0, 0],
    'B': [0, 2, 3],
    'C': [0, 3, 2]
}

Each index represents a ranking position. 3. Process every vote.

For each vote string:

• Traverse each position
• Increment the corresponding positional counter for that team

Example:

Vote "ACB" means:

• A gets one first place vote
• C gets one second place vote
• B gets one third place vote

4. Extract all teams into a sortable list.

We need a list of team characters because we will sort them according to ranking rules. 5. Sort teams using a custom comparison key.

Teams should be sorted by:

• Highest first place votes
• Highest second place votes
• Highest third place votes
• Continue for all positions
• Alphabetical order if still tied

In Python, we can achieve descending positional order by negating counts.

Example sort key:

(-count1, -count2, -count3, team_letter)

6. Join the sorted teams into the final string.

After sorting, concatenate the characters into the result.

Why it works

The algorithm works because the ranking rules define a lexicographic comparison over positional vote counts.

Each team is represented by a vector:

[first_place_votes, second_place_votes, third_place_votes, ...]

Sorting teams lexicographically by these vectors exactly matches the problem definition. If two vectors are identical, alphabetical ordering provides the final deterministic tie breaker.

Because every vote contributes exactly once to the correct positional counter, the precomputed statistics are accurate, and the sorting order is guaranteed to match the required ranking system.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        if not votes:
            return ""

        team_count = len(votes[0])

        rank_counts = defaultdict(lambda: [0] * team_count)

        for vote in votes:
            for position, team in enumerate(vote):
                rank_counts[team][position] += 1

        teams = list(votes[0])

        teams.sort(
            key=lambda team: (
                [-count for count in rank_counts[team]],
                team
            )
        )

        return "".join(teams)

The implementation begins by handling the edge case where the input is empty. Although the constraints guarantee at least one vote, this defensive check makes the function safer.

We determine the number of teams using the first vote. Since every vote contains all teams exactly once, this gives the correct size for all positional count arrays.

The defaultdict stores ranking statistics for every team. Each team maps to a list where index i stores how many times that team appeared in position i.

While processing votes, we iterate through every character and increment the appropriate positional counter.

After preprocessing, we create a list of teams from votes[0]. This works because every team appears in every vote.

The custom sort key is the most important part of the solution. We negate counts so that larger counts appear earlier in ascending sort order. The team character itself is appended to the key to enforce alphabetical ordering for complete ties.

Finally, we join the sorted teams into the answer string.

Go Solution

package main

import (
	"sort"
)

func rankTeams(votes []string) string {
	if len(votes) == 0 {
		return ""
	}

	teamCount := len(votes[0])

	rankCounts := make(map[byte][]int)

	for i := 0; i < teamCount; i++ {
		team := votes[0][i]
		rankCounts[team] = make([]int, teamCount)
	}

	for _, vote := range votes {
		for position := 0; position < teamCount; position++ {
			team := vote[position]
			rankCounts[team][position]++
		}
	}

	teams := []byte(votes[0])

	sort.Slice(teams, func(i, j int) bool {
		teamA := teams[i]
		teamB := teams[j]

		for position := 0; position < teamCount; position++ {
			if rankCounts[teamA][position] != rankCounts[teamB][position] {
				return rankCounts[teamA][position] > rankCounts[teamB][position]
			}
		}

		return teamA < teamB
	})

	return string(teams)
}

The Go solution follows the same algorithmic structure as the Python version, but the implementation details differ slightly.

Go does not support custom tuple based sorting keys as conveniently as Python, so we use sort.Slice with a comparator function. The comparator manually checks positional vote counts one by one.

The vote statistics are stored in map[byte][]int because team identifiers are uppercase ASCII characters.

Go slices are mutable, so sorting happens directly on the teams slice.

There are no integer overflow concerns because vote counts are at most 1000.

Worked Examples

Example 1

votes = ["ABC","ACB","ABC","ACB","ACB"]

Step 1: Initialize Counts

Team	1st	2nd	3rd
A	0	0	0
B	0	0	0
C	0	0	0

Step 2: Process Each Vote

Process "ABC":

Team	1st	2nd	3rd
A	1	0	0
B	0	1	0
C	0	0	1

Process "ACB":

Team	1st	2nd	3rd
A	2	0	0
B	0	1	1
C	0	1	1

Process remaining votes:

Team	1st	2nd	3rd
A	5	0	0
B	0	2	3
C	0	3	2

Step 3: Sort Teams

Compare B and C:

• First place votes: tie

• Second place votes:

• B = 2

• C = 3

So C ranks ahead of B.

Final ranking:

"ACB"

Example 2

votes = ["WXYZ","XYZW"]

Final Counts

Team	1st	2nd	3rd	4th
W	1	0	0	1
X	1	1	0	0
Y	0	1	1	0
Z	0	0	1	1

Sorting

Compare W and X:

• First place votes: both 1

• Second place votes:

• W = 0

• X = 1

So X ranks ahead of W.

Final answer:

"XWYZ"

Example 3

votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]

Only one vote exists, so every team already has a unique ranking.

The frequency table directly mirrors the input ordering.

Final answer:

"ZMNAGUEDSJYLBOPHRQICWFXTVK"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V × T + T log T)	Counting votes takes V × T, sorting takes T log T
Space	O(T²)	Each team stores an array of size T

Where:

• V is the number of votes
• T is the number of teams

The counting phase processes every character in every vote exactly once. The sorting phase handles at most 26 teams, so it is effectively constant time in practice.

The space usage comes from storing positional vote counts for every team.

Test Cases

from typing import List

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        from collections import defaultdict

        if not votes:
            return ""

        team_count = len(votes[0])

        rank_counts = defaultdict(lambda: [0] * team_count)

        for vote in votes:
            for position, team in enumerate(vote):
                rank_counts[team][position] += 1

        teams = list(votes[0])

        teams.sort(
            key=lambda team: (
                [-count for count in rank_counts[team]],
                team
            )
        )

        return "".join(teams)

solution = Solution()

assert solution.rankTeams(
    ["ABC", "ACB", "ABC", "ACB", "ACB"]
) == "ACB"  # Basic ranking comparison

assert solution.rankTeams(
    ["WXYZ", "XYZW"]
) == "XWYZ"  # Tie resolved using second-place votes

assert solution.rankTeams(
    ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
) == "ZMNAGUEDSJYLBOPHRQICWFXTVK"  # Single voter case

assert solution.rankTeams(
    ["ABC", "BAC", "CBA"]
) == "ABC"  # Multiple layered tie breaks

assert solution.rankTeams(
    ["BCA", "CAB", "ACB"]
) == "ABC"  # Complete tie resolved alphabetically

assert solution.rankTeams(
    ["A"]
) == "A"  # Single team

assert solution.rankTeams(
    ["MNO", "MNO", "MNO"]
) == "MNO"  # All votes identical

assert solution.rankTeams(
    ["ABCDEF", "FEDCBA", "ABCDEF", "FEDCBA"]
) == "ABCDEF"  # Large tie structure

print("All test cases passed!")

Test	Why
["ABC","ACB","ABC","ACB","ACB"]	Validates normal ranking behavior
["WXYZ","XYZW"]	Validates tie resolution using later positions
["ZMNAGUEDSJYLBOPHRQICWFXTVK"]	Validates single vote handling
["ABC","BAC","CBA"]	Validates deeper positional comparisons
["BCA","CAB","ACB"]	Validates alphabetical tie breaking
["A"]	Validates smallest possible input
["MNO","MNO","MNO"]	Validates repeated identical votes
["ABCDEF","FEDCBA","ABCDEF","FEDCBA"]	Validates complex balanced vote distributions

Edge Cases

Complete Tie Between Teams

A particularly tricky scenario occurs when two or more teams receive identical counts at every ranking position. In this situation, the problem requires alphabetical ordering as the final tie breaker.

For example:

["ABC", "BCA", "CAB"]

Every team receives one first place vote, one second place vote, and one third place vote.

A buggy implementation might produce inconsistent ordering depending on sort stability. Our implementation explicitly appends the team letter to the sorting key, guaranteeing deterministic alphabetical ordering.

Only One Vote Exists

When there is only one voter, the result should exactly match that vote because no aggregation or conflict resolution is necessary.

Example:

["ZMNAGU"]

A careless implementation might unnecessarily reorder teams or mishandle missing counts. Our frequency counting naturally handles this because each team receives exactly one vote in its respective position.

Tie Broken at Deep Positions

Some teams may remain tied for several ranking levels before finally differing later.

Example:

["ABC", "ACB"]

Both B and C have:

• Zero first place votes
• One second place vote
• One third place vote

But depending on other votes, ties can extend across many positions.

An incorrect implementation that only checks first or second place votes would fail. Our comparator examines all ranking positions sequentially, ensuring the correct lexicographic comparison across the entire ranking vector.