0531MediumArrayHash TableStringSortingCounting

Ranking Dessert Entries by Judge Cards

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Each judge at a bake-off hands in a card ranking every entry from best to worst. An entry is written as one uppercase letter, and ballots[i] is the i-th judge's card, read left to right from their first place to their last. Every card lists exactly the same entries, each of them once.

The final table is worked out place by place. The entry named first on more cards finishes ahead. If two entries were named first on the same number of cards, whichever of them was named second on more cards finishes ahead, then third place is compared, and so on. If two entries have exactly the same count at every place, the one whose letter comes earlier in the alphabet finishes ahead.

Return the entries in final order as a single string.

Examples

Example 1

Input: ballots = ["ACB", "BCA", "CBA"]
Output: "CBA"

Each entry is named first on exactly one card, so first place is compared next: C is named second twice, B once and A never. The table therefore reads C, then B, then A.

Example 2

Input: ballots = ["ABC", "CBA", "CBA"]
Output: "CAB"

C is named first twice, A once and B never, which fixes the whole table as C, then A, then B.

Example 3

Input: ballots = ["BA", "AB"]
Output: "AB"

A and B are each named first once and second once, so their counts match at every place and the alphabet puts A ahead.

Constraints

1 <= ballots.length <= 1000
1 <= ballots[i].length <= 26
All cards have the same length.
ballots[i][j] is an uppercase English letter.
No card names the same entry twice.
Every card names exactly the entries that ballots[0] names.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def rank_entries(ballots: list[str]) -> str:

Java

public String rankEntries(String[] ballots)

The intended approach

Time O(m * w + w * k log k) for m cards of width w over k entries.Space O(k * w) for the counter rows.

Give every entry a row of counters, one per place on a card, and fill them by reading each card once. Comparing two entries then means comparing their rows left to right, which is exactly what ordering the rows as sequences does once each count is negated so that a larger count sorts earlier. Appending the letter itself to the sort key settles the entries whose rows match completely.

Pythonentry point: rank_entries

def rank_entries(ballots):
    # O(m*w + w * k log k): tally how often each entry lands in each place, then
    # order the entries on that tally with the letter as the final decider.
    width = len(ballots[0])
    table = {}
    for ch in ballots[0]:
        table[ch] = [0] * width
    for card in ballots:
        for place in range(width):
            table[card[place]][place] += 1
    keys = sorted(table.keys(),
                  key=lambda ch: ([-count for count in table[ch]], ch))
    return "".join(keys)

The obvious version

Pick the winner by repeated selection: hold a current leader and challenge it with every remaining entry, recounting each place across all the cards until one of them differs, and falling back on the letters when nothing does. Remove the winner and repeat.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_rank_entries(ballots):
    width = len(ballots[0])

    def tally(letter, place):
        found = 0
        for card in ballots:
            if card[place] == letter:
                found += 1
        return found

    pool = sorted(set(ballots[0]))
    out = []
    while pool:
        lead = pool[0]
        for other in pool[1:]:
            wins = False
            for place in range(width):
                mine = tally(other, place)
                theirs = tally(lead, place)
                if mine != theirs:
                    wins = mine > theirs
                    break
            else:
                wins = other < lead
            if wins:
                lead = other
        out.append(lead)
        pool.remove(lead)
    return "".join(out)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in