FastPrep
Problem · Array

Popular and Instant-Runoff Election Winners

Learn this problem
● HardCoursera logoCourseraFULLTIMEPHONE SCREEN

Problem statement

An election has weighted ranked ballots. Each row of rankings lists every candidate exactly once, from most preferred to least preferred. The matching value in ballotCounts is the number of voters who submitted that ranking.

Return a two-element array:

  1. The popular winner: the candidate with the greatest total weight in first place. If several candidates tie, choose the lexicographically smallest name.
  2. The instant-runoff winner: repeatedly count each ballot for its highest-ranked candidate who has not been eliminated. A candidate wins immediately upon receiving strictly more than half of all ballot weight. Otherwise, eliminate the candidate with the smallest current total. If several candidates tie for the smallest total, eliminate the lexicographically largest one. Continue until a candidate has a strict majority or only one candidate remains.

Candidate names are compared by case-sensitive ASCII lexicographic order. Repeated ranking rows remain separate weighted ballots; if eliminations make several rows share the same remaining order, all of their weights still contribute.

Interview follow-up

A later report says the interviewer asked for the tradeoffs between sorting map values and scanning every map entry to find a maximum.

Function

electionWinners(rankings: String[][], ballotCounts: int[]) → String[]

Examples

Example 1

rankings = [["A","B","C"],["B","C","A"],["C","B","A"]]ballotCounts = [4,3,2]return = ["A","B"]

A has the largest initial total with 4 votes, so it is the popular winner. No candidate has more than half of the 9 votes. Eliminating C transfers its 2 votes to B, which then has 5 votes and wins the runoff.

Example 2

rankings = [["Ada","Bob"],["Bob","Ada"]]ballotCounts = [6,4]return = ["Ada","Ada"]

Ada starts with 6 of 10 votes, so the same candidate wins both calculations without an elimination.

Example 3

rankings = [["A","B","C"],["B","A","C"],["C","B","A"]]ballotCounts = [1,1,1]return = ["A","B"]

All three candidates initially tie, so the popular tie-break chooses A. The runoff tie-break eliminates lexicographically largest C; that ballot transfers to B, which wins 2 to 1.

Constraints

  • 1 <= rankings.length == ballotCounts.length <= 50.
  • 1 <= rankings[i].length <= 20.
  • Every row contains the same candidates exactly once.
  • 1 <= candidate.length <= 20, and each candidate contains only uppercase or lowercase ASCII letters.
  • 1 <= ballotCounts[i] <= 100000.
  • The total ballot weight fits in a signed 32-bit integer.
drafts saved locally
public String[] electionWinners(String[][] rankings, int[] ballotCounts) {
    // write your code here
}
rankings[["A","B","C"],["B","C","A"],["C","B","A"]]
ballotCounts[4,3,2]
expected["A", "B"]
checking account