unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1366: Rank Teams by Votes

link

Say there are n positions and v = (c_1, c_2, \ldots, c_n) represents the vote counts for \texttt{team} at different positions. Like, \texttt{team} got c_1 votes for position 1, got c_2 votes for position 2, etc. We can consider an extended pair: (v, \texttt{team}) and sort these pairs by reverse-lexicographic of the first element and lexicographic of the second element.

To have custom comparison while sorting we encapsulate each team’s vote counts in a Rank object.

Say there are n votes and m teams.

Time: \mathcal{O}(n \cdot m + m^2 \cdot \lg{m}), space: \mathcal{O}(m^2).

class Rank:
    def __init__(self, tally, team):
        self.tally = tally
        self.team = team

    def update(self, i):
        self.tally[i] += 1

    def __lt__(self, other):
        if self.tally != other.tally:
            return self.tally >= other.tally

        return self.team < other.team


class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        ranks = {t: Rank([0] * len(votes[0]), t) for t in votes[0]}
        for v in votes:
            for i, t in enumerate(v):
                ranks[t].update(i)

        return "".join([r.team for r in sorted(ranks.values())])

tanvirdotzaman

,

Leave a comment