Rank Teams by Votes — LeetCode 1366 Python Solution

The 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.

Example

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.

Python solution

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1366. Rank Teams by Votes is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems