Problem

Table: Votes

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| voter       | varchar |
| candidate   | varchar |
+-------------+---------+
(voter, candidate) is the primary key (combination of unique values) for this table.
Each row of this table contains name of the voter and their candidate.

The election is conducted in a city where everyone can vote for one or more candidates or choose not to vote. Each person has 1vote so if they vote for multiple candidates, their vote gets equally split across them. For example, if a person votes for 2 candidates, these candidates receive an equivalent of 0.5 votes each.

Write a solution to find candidate who got the most votes and won the election. Output the name of the candidate or If multiple candidates have an equal number of votes, display the names of all of them.

Return the result table ordered by candidate inascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Input: 
Votes table:
+----------+-----------+
| voter    | candidate |
+----------+-----------+
| Kathy    | null      |
| Charles  | Ryan      |
| Charles  | Christine |
| Charles  | Kathy     |
| Benjamin | Christine |
| Anthony  | Ryan      |
| Edward   | Ryan      |
| Terry    | null      |
| Evelyn   | Kathy     |
| Arthur   | Christine |
+----------+-----------+
Output: 
+-----------+
| candidate | 
+-----------+
| Christine |  
| Ryan      |  
+-----------+
Explanation: 
- Kathy and Terry opted not to participate in voting, resulting in their votes being recorded as 0. Charles distributed his vote among three candidates, equating to 0.33 for each candidate. On the other hand, Benjamin, Arthur, Anthony, Edward, and Evelyn each cast their votes for a single candidate.
- Collectively, Candidate Ryan and Christine amassed a total of 2.33 votes, while Kathy received a combined total of 1.33 votes.
Since Ryan and Christine received an equal number of votes, we will display their names in ascending order.

Solution

Method 1 – SQL Window Functions and Grouping

Intuition

Each voter can vote for multiple candidates, so each vote is worth 1/count for that voter. We sum the fractional votes for each candidate, then select the candidate(s) with the highest total. If there is a tie, return all such candidates in ascending order.

Approach

  1. For each voter, count how many candidates they voted for.
  2. For each (voter, candidate), assign a fractional vote of 1/count.
  3. Sum the fractional votes for each candidate.
  4. Find the maximum total vote.
  5. Return all candidates with the maximum vote, ordered by candidate ascending.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

WITH vote_counts AS (
  SELECT voter, COUNT(*) AS cnt
  FROM Votes
  GROUP BY voter
),
weighted_votes AS (
  SELECT v.candidate, 1.0 / vc.cnt AS vote
  FROM Votes v
  JOIN vote_counts vc ON v.voter = vc.voter
),
sum_votes AS (
  SELECT candidate, SUM(vote) AS total_votes
  FROM weighted_votes
  GROUP BY candidate
),
max_vote AS (
  SELECT MAX(total_votes) AS max_votes FROM sum_votes
)
SELECT candidate
FROM sum_votes, max_vote
WHERE total_votes = max_votes
ORDER BY candidate ASC;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

WITH vote_counts AS (
  SELECT voter, COUNT(*) AS cnt
  FROM Votes
  GROUP BY voter
),
weighted_votes AS (
  SELECT v.candidate, 1.0 / vc.cnt AS vote
  FROM Votes v
  JOIN vote_counts vc ON v.voter = vc.voter
),
sum_votes AS (
  SELECT candidate, SUM(vote) AS total_votes
  FROM weighted_votes
  GROUP BY candidate
),
max_vote AS (
  SELECT MAX(total_votes) AS max_votes FROM sum_votes
)
SELECT candidate
FROM sum_votes, max_vote
WHERE total_votes = max_votes
ORDER BY candidate ASC;
1
2
3
4
5
6
7
8
9

import pandas as pd

def election_results(votes: pd.DataFrame) -> pd.DataFrame:
    counts = votes.groupby('voter').candidate.transform('count')
    votes['fraction'] = 1 / counts
    res = votes.groupby('candidate', as_index=False)['fraction'].sum()
    max_votes = res['fraction'].max()
    winners = res[res['fraction'] == max_votes].sort_values('candidate')[['candidate']]
    return winners

Complexity

  • ⏰ Time complexity: O(n), where n is the number of votes.
  • 🧺 Space complexity: O(n), for intermediate tables.