LeetCode 2820 - Election Results

The Votes table records every voter-candidate selection. A voter may vote for multiple candidates, vote for exactly one candidate, or choose not to vote at all. The important detail is that every voter contributes a total voting weight of exactly 1.

leetcodemedium

LeetCode Problem 2820

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The Votes table records every voter-candidate selection. A voter may vote for multiple candidates, vote for exactly one candidate, or choose not to vote at all. The important detail is that every voter contributes a total voting weight of exactly 1.

If a voter selects:

  • One candidate, that candidate receives 1.0 vote.
  • Two candidates, each candidate receives 0.5 votes.
  • Three candidates, each candidate receives 1/3 votes.
  • No candidate (candidate IS NULL), nobody receives any portion of that vote.

The task is to compute the total vote count received by every candidate after all vote splitting has been applied. Once all candidate totals have been calculated, we must identify the maximum vote total and return every candidate whose total equals that maximum value.

The output should contain a single column, candidate, listing all winners in ascending alphabetical order.

The input represents a collection of voting records. Multiple rows can belong to the same voter because a voter may support multiple candidates. The primary key (voter, candidate) guarantees that the same voter cannot vote for the same candidate twice.

An important observation is that vote distribution depends on the number of candidates selected by each voter. Therefore, before calculating candidate totals, we must know how many candidates each voter selected.

Several edge cases must be handled correctly:

  • A voter may have only a NULL candidate entry, meaning they participated in the election process but cast no vote.
  • Multiple candidates may tie for first place.
  • Every voter may vote for a different number of candidates.
  • Fractional vote values must be computed accurately.
  • Candidates receiving votes from many split ballots must have all contributions summed correctly.

Approaches

Brute Force

A straightforward approach is to process each candidate separately.

For every candidate, iterate through all rows and determine how much vote contribution each row provides. To compute a row's contribution, we must count how many candidates the corresponding voter selected. This counting step may require scanning the table repeatedly.

This approach is correct because every candidate's total is computed by explicitly evaluating every possible vote contribution. However, it performs redundant work. The same voter's candidate count may be recomputed many times, causing unnecessary repeated scans of the table.

As the dataset grows, repeatedly recalculating voter selections becomes increasingly expensive.

Key Insight

The critical observation is that a voter's contribution depends only on the number of non-null candidates they selected.

If a voter selected k candidates, each selected candidate receives exactly 1/k votes.

Therefore:

  1. Compute k for every voter.
  2. For every non-null vote record, contribute 1/k to the selected candidate.
  3. Aggregate candidate totals.
  4. Find the maximum total.
  5. Return all candidates matching that maximum.

In SQL, this naturally translates into:

  • A grouping operation to count candidate selections per voter.
  • A join back to the original table.
  • A second grouping operation to compute candidate totals.
  • A final filter selecting candidates whose totals equal the maximum score.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly recomputes voter selection counts
Optimal O(n) O(n) Compute voter counts once, then aggregate candidate totals

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Group rows by voter and count the number of non-null candidates selected by each voter. This gives the denominator needed for vote splitting.
  2. Join this voter-count result back to the original Votes table. Every vote record now knows how many candidates its voter selected.
  3. Ignore rows whose candidate is NULL, because they contribute no votes to any candidate.
  4. For every non-null vote record, compute its contribution as:

1 / candidate_count 5. Group by candidate and sum all contributions. The result is the final vote total for every candidate. 6. Find the largest vote total among all candidates. 7. Return every candidate whose total equals that maximum value. 8. Sort the resulting candidate names in ascending order.

Why it works

Every voter contributes exactly one unit of voting power. If a voter selects k candidates, assigning 1/k to each candidate ensures the total distributed vote remains exactly 1. Summing these contributions across all voters produces the correct election totals. Selecting candidates whose totals equal the maximum value therefore identifies exactly the election winner or winners.

Python Solution

Although this is a SQL problem on LeetCode, the following Python implementation demonstrates the underlying algorithm.

from collections import defaultdict
from typing import List, Tuple

class Solution:
    def electionResults(
        self,
        votes: List[Tuple[str, str | None]]
    ) -> List[str]:

        voter_counts = defaultdict(int)

        for voter, candidate in votes:
            if candidate is not None:
                voter_counts[voter] += 1

        candidate_scores = defaultdict(float)

        for voter, candidate in votes:
            if candidate is not None:
                candidate_scores[candidate] += 1.0 / voter_counts[voter]

        max_score = max(candidate_scores.values())

        winners = [
            candidate
            for candidate, score in candidate_scores.items()
            if abs(score - max_score) < 1e-9
        ]

        return sorted(winners)

The implementation first counts how many candidates each voter selected. This count determines the fraction allocated to each chosen candidate.

Next, every non-null vote contributes 1 / voter_count to the candidate's accumulated score.

After all scores are computed, the maximum score is determined. Every candidate matching that maximum score is collected and returned in sorted order.

Go Solution

package main

import (
	"math"
	"sort"
)

func electionResults(votes [][2]string) []string {
	voterCounts := make(map[string]int)

	for _, vote := range votes {
		voter := vote[0]
		candidate := vote[1]

		if candidate != "" {
			voterCounts[voter]++
		}
	}

	candidateScores := make(map[string]float64)

	for _, vote := range votes {
		voter := vote[0]
		candidate := vote[1]

		if candidate != "" {
			candidateScores[candidate] += 1.0 / float64(voterCounts[voter])
		}
	}

	maxScore := 0.0
	for _, score := range candidateScores {
		if score > maxScore {
			maxScore = score
		}
	}

	var winners []string

	for candidate, score := range candidateScores {
		if math.Abs(score-maxScore) < 1e-9 {
			winners = append(winners, candidate)
		}
	}

	sort.Strings(winners)
	return winners
}

The Go version follows exactly the same logic as the Python solution. Maps are used for both voter counts and candidate score aggregation. Floating point comparisons use a small epsilon to avoid precision issues when comparing vote totals.

SQL Solution

The actual LeetCode submission should be written in SQL.

WITH voter_counts AS (
    SELECT
        voter,
        COUNT(candidate) AS cnt
    FROM Votes
    GROUP BY voter
),
candidate_votes AS (
    SELECT
        v.candidate,
        SUM(1.0 / vc.cnt) AS total_votes
    FROM Votes v
    JOIN voter_counts vc
        ON v.voter = vc.voter
    WHERE v.candidate IS NOT NULL
    GROUP BY v.candidate
)
SELECT candidate
FROM candidate_votes
WHERE total_votes = (
    SELECT MAX(total_votes)
    FROM candidate_votes
)
ORDER BY candidate;

The first CTE computes how many candidates each voter selected. The second CTE calculates total votes received by each candidate after vote splitting. Finally, candidates matching the maximum vote total are returned in ascending order.

Worked Examples

Example 1

Input:

voter candidate
Kathy NULL
Charles Ryan
Charles Christine
Charles Kathy
Benjamin Christine
Anthony Ryan
Edward Ryan
Terry NULL
Evelyn Kathy
Arthur Christine

Step 1: Count selections per voter

voter candidate count
Charles 3
Benjamin 1
Anthony 1
Edward 1
Evelyn 1
Arthur 1
Kathy 0
Terry 0

Step 2: Distribute votes

voter candidate contribution
Charles Ryan 1/3
Charles Christine 1/3
Charles Kathy 1/3
Benjamin Christine 1
Anthony Ryan 1
Edward Ryan 1
Evelyn Kathy 1
Arthur Christine 1

Step 3: Aggregate candidate totals

candidate total
Ryan 1/3 + 1 + 1 = 2.3333
Christine 1/3 + 1 + 1 = 2.3333
Kathy 1/3 + 1 = 1.3333

Step 4: Determine winners

Maximum total:

candidate total
Christine 2.3333
Ryan 2.3333

Output:

candidate
Christine
Ryan

Complexity Analysis

SQL Solution

Measure Complexity Explanation
Time O(n) Each row participates in a constant number of grouping and aggregation operations
Space O(n) Aggregation tables store voter counts and candidate totals

The solution performs two main aggregation passes over the data. Modern database engines implement grouping with hashing or sorting, making the overall work proportional to the size of the input table.

Test Cases

def election_results(votes):
    from collections import defaultdict

    voter_counts = defaultdict(int)

    for voter, candidate in votes:
        if candidate is not None:
            voter_counts[voter] += 1

    candidate_scores = defaultdict(float)

    for voter, candidate in votes:
        if candidate is not None:
            candidate_scores[candidate] += 1.0 / voter_counts[voter]

    max_score = max(candidate_scores.values())

    return sorted(
        candidate
        for candidate, score in candidate_scores.items()
        if abs(score - max_score) < 1e-9
    )

assert election_results([
    ("Kathy", None),
    ("Charles", "Ryan"),
    ("Charles", "Christine"),
    ("Charles", "Kathy"),
    ("Benjamin", "Christine"),
    ("Anthony", "Ryan"),
    ("Edward", "Ryan"),
    ("Terry", None),
    ("Evelyn", "Kathy"),
    ("Arthur", "Christine")
]) == ["Christine", "Ryan"]  # official example

assert election_results([
    ("A", "John")
]) == ["John"]  # single voter, single candidate

assert election_results([
    ("A", "John"),
    ("B", "Mary")
]) == ["John", "Mary"]  # perfect tie

assert election_results([
    ("A", "John"),
    ("A", "Mary")
]) == ["John", "Mary"]  # split vote equally

assert election_results([
    ("A", None),
    ("B", "John")
]) == ["John"]  # abstaining voter

assert election_results([
    ("A", "John"),
    ("A", "Mary"),
    ("A", "Bob"),
    ("B", "John")
]) == ["John"]  # fractional plus full vote

assert election_results([
    ("A", "John"),
    ("B", "John"),
    ("C", "Mary"),
    ("D", "Mary")
]) == ["John", "Mary"]  # tie after aggregation

Test Summary

Test Why
Official example Validates vote splitting and tie handling
Single voter Smallest meaningful election
Two candidates tie Confirms multiple winners are returned
One voter selects two candidates Verifies equal vote distribution
Abstaining voter Ensures NULL votes contribute nothing
Fractional plus full votes Tests aggregation of mixed vote weights
Aggregate tie Verifies maximum score filtering

Edge Cases

Voters Who Do Not Vote

A voter may appear only with a NULL candidate. Such voters contribute no vote to any candidate. A common bug is accidentally including these rows when computing candidate totals. The implementation explicitly ignores NULL candidates during vote distribution.

Multiple Candidates Selected by One Voter

A voter may support several candidates. The most common mistake is counting each selection as a full vote, which would allow a voter to contribute more than one total vote. The solution first computes the number of selected candidates and allocates exactly 1/k to each, preserving the voter's total voting power.

Multiple Winners

Several candidates may finish with exactly the same vote total. Returning only one candidate would be incorrect. After computing all totals, the solution identifies the maximum score and returns every candidate whose score matches that value.

Fractional Vote Totals

Because votes are split, totals may contain repeating decimals such as 1/3. Comparing floating point values carelessly can produce incorrect results. The implementation uses tolerance-based comparisons in procedural languages, while the SQL solution relies on exact aggregation of identical expressions and comparison against the computed maximum from the same aggregation result.

All Support Concentrated on One Candidate

If every voter ultimately contributes to a single candidate, that candidate should be returned alone. The aggregation logic naturally handles this case because the maximum total belongs uniquely to that candidate.