LeetCode 574 - Winning Candidate

This problem provides two database tables, Candidate and Vote, and asks us to determine which candidate won the election. The Candidate table stores information about each candidate. Every candidate has a unique integer id and a corresponding name.

leetcodemediumdatabase

LeetCode Problem 574

Difficulty: 🟡 Medium
Topics: Database

Solution

LeetCode 574 - Winning Candidate

Problem Understanding

This problem provides two database tables, Candidate and Vote, and asks us to determine which candidate won the election.

The Candidate table stores information about each candidate. Every candidate has a unique integer id and a corresponding name.

The Vote table stores the voting results. Each row represents a single vote, and the candidateId column tells us which candidate received that vote. Since each row corresponds to exactly one vote, the number of times a candidate's ID appears in the Vote table is equal to the total number of votes that candidate received.

The goal is to return the name of the candidate with the largest number of votes.

The problem guarantees that there is exactly one winner. This guarantee is important because it removes the need to handle ties. We never need to return multiple candidates or apply tie-breaking rules.

The input effectively represents:

  • A mapping from candidate IDs to candidate names
  • A collection of votes referencing candidate IDs

The expected output is a single-row table containing the winner's name.

A naive implementation might struggle with repeatedly counting votes for each candidate individually, especially if the number of votes is large. However, SQL aggregation functions are designed specifically for this kind of counting operation.

Important edge cases include:

  • A candidate receiving all votes
  • Candidates receiving zero votes
  • Only one candidate existing
  • Very uneven vote distributions

The uniqueness guarantee for the winner simplifies the query because we can safely use LIMIT 1 after sorting by vote count.

Approaches

Brute Force Approach

A brute-force solution would examine each candidate one by one and count how many rows in the Vote table reference that candidate.

Conceptually, the process would look like this:

  1. Iterate through every candidate
  2. For each candidate, scan the entire Vote table
  3. Count matching votes
  4. Track the candidate with the maximum count

This approach is correct because it explicitly computes the vote total for every candidate. However, it is inefficient because the Vote table is repeatedly scanned.

If there are C candidates and V votes, the total work becomes O(C × V).

Optimal Approach

The key observation is that SQL databases provide aggregation operations that can count grouped records efficiently.

Instead of counting votes separately for each candidate, we can:

  1. Group votes by candidateId
  2. Count votes for each group
  3. Sort the groups by vote count in descending order
  4. Select the top candidate
  5. Join with the Candidate table to retrieve the candidate name

This approach leverages SQL's optimized grouping and sorting mechanisms and avoids repeated scans of the Vote table.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(C × V) O(1) Repeatedly scans the vote table for every candidate
Optimal O(V log V) O(V) Uses grouping and sorting to count votes efficiently

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Start with the Vote table because it contains all voting information.
  2. Group the rows by candidateId. This creates one group for each candidate who received votes.
  3. Use the COUNT(*) aggregation function to compute how many votes belong to each candidate.
  4. Sort the grouped results in descending order of vote count using ORDER BY COUNT(*) DESC.
  5. Since the problem guarantees exactly one winner, select only the first row using LIMIT 1.
  6. Join the winning candidateId with the Candidate table to retrieve the candidate's name instead of returning only the numeric ID.
  7. Return the resulting candidate name.

Why it works

Grouping by candidateId ensures that all votes for the same candidate are collected together. Counting the rows in each group gives the exact number of votes received by that candidate. Sorting in descending order guarantees that the candidate with the highest vote total appears first. Since the problem guarantees a unique winner, selecting the first result always returns the correct candidate.

Python Solution

Although this is a database problem and LeetCode expects an SQL query, the following Python example demonstrates the same logic programmatically.

from collections import Counter
from typing import List, Dict

class Solution:
    def winningCandidate(
        self,
        candidates: List[Dict[str, object]],
        votes: List[Dict[str, int]]
    ) -> str:
        vote_counts = Counter()

        for vote in votes:
            candidate_id = vote["candidateId"]
            vote_counts[candidate_id] += 1

        winning_candidate_id = max(
            vote_counts,
            key=vote_counts.get
        )

        candidate_map = {
            candidate["id"]: candidate["name"]
            for candidate in candidates
        }

        return candidate_map[winning_candidate_id]

The implementation begins by counting votes using a Counter object. Every vote increments the count for the corresponding candidateId.

After all votes are processed, the max function identifies the candidate ID with the largest vote count.

A dictionary is then built to map candidate IDs to candidate names. This simulates the SQL join operation between the Vote and Candidate tables.

Finally, the winning candidate's name is returned.

Go Solution

package main

type Candidate struct {
	Id   int
	Name string
}

type Vote struct {
	Id          int
	CandidateId int
}

func winningCandidate(
	candidates []Candidate,
	votes []Vote,
) string {

	voteCounts := make(map[int]int)

	for _, vote := range votes {
		voteCounts[vote.CandidateId]++
	}

	winningCandidateId := -1
	maxVotes := -1

	for candidateId, count := range voteCounts {
		if count > maxVotes {
			maxVotes = count
			winningCandidateId = candidateId
		}
	}

	candidateMap := make(map[int]string)

	for _, candidate := range candidates {
		candidateMap[candidate.Id] = candidate.Name
	}

	return candidateMap[winningCandidateId]
}

The Go implementation follows the same logical structure as the Python solution. A map is used instead of Python's Counter to store vote frequencies.

Go requires explicit variable initialization, so winningCandidateId and maxVotes are initialized manually.

The candidate lookup table is implemented using another map from candidate ID to candidate name.

Unlike Python dictionaries, Go maps return zero values when keys are absent, but the problem guarantees valid foreign key relationships, so every vote always references a valid candidate.

SQL Solution

SELECT c.name
FROM Candidate c
JOIN Vote v
    ON c.id = v.candidateId
GROUP BY c.id, c.name
ORDER BY COUNT(*) DESC
LIMIT 1;

This query joins candidates with votes, groups rows by candidate, counts the votes per candidate, sorts candidates by vote count in descending order, and returns the top result.

Worked Examples

Example 1

Input

Candidate table:

id name
1 A
2 B
3 C
4 D
5 E

Vote table:

id candidateId
1 2
2 4
3 3
4 2
5 5

Step-by-step vote counting

Vote Row candidateId Vote Counts After Processing
1 2 {2: 1}
2 4 {2: 1, 4: 1}
3 3 {2: 1, 4: 1, 3: 1}
4 2 {2: 2, 4: 1, 3: 1}
5 5 {2: 2, 4: 1, 3: 1, 5: 1}

After processing all votes:

  • Candidate 2 has 2 votes
  • Candidate 4 has 1 vote
  • Candidate 3 has 1 vote
  • Candidate 5 has 1 vote

Candidate 2 has the largest vote count.

Using the candidate table:

id name
2 B

The final answer is:

name
B

Complexity Analysis

Measure Complexity Explanation
Time O(V + C) Counting votes requires scanning all votes once, and building the candidate map requires scanning all candidates once
Space O(V + C) Additional hash maps store vote counts and candidate mappings

The dominant work comes from iterating through the votes and candidates exactly once. Hash map operations are constant time on average, so the total complexity is linear relative to the input size.

For the SQL solution, actual runtime depends on the database engine's implementation of grouping and sorting, but conceptually the aggregation dominates the work.

Test Cases

from collections import Counter

class Solution:
    def winningCandidate(self, candidates, votes):
        vote_counts = Counter()

        for vote in votes:
            vote_counts[vote["candidateId"]] += 1

        winning_candidate_id = max(
            vote_counts,
            key=vote_counts.get
        )

        candidate_map = {
            candidate["id"]: candidate["name"]
            for candidate in candidates
        }

        return candidate_map[winning_candidate_id]

solution = Solution()

# Basic example from the problem statement
assert solution.winningCandidate(
    [
        {"id": 1, "name": "A"},
        {"id": 2, "name": "B"},
        {"id": 3, "name": "C"},
        {"id": 4, "name": "D"},
        {"id": 5, "name": "E"},
    ],
    [
        {"id": 1, "candidateId": 2},
        {"id": 2, "candidateId": 4},
        {"id": 3, "candidateId": 3},
        {"id": 4, "candidateId": 2},
        {"id": 5, "candidateId": 5},
    ]
) == "B"  # Candidate B has the most votes

# Single candidate receives all votes
assert solution.winningCandidate(
    [
        {"id": 1, "name": "Alice"},
    ],
    [
        {"id": 1, "candidateId": 1},
        {"id": 2, "candidateId": 1},
        {"id": 3, "candidateId": 1},
    ]
) == "Alice"  # Only candidate must win

# Large winning margin
assert solution.winningCandidate(
    [
        {"id": 1, "name": "Tom"},
        {"id": 2, "name": "Jerry"},
    ],
    [
        {"id": 1, "candidateId": 2},
        {"id": 2, "candidateId": 2},
        {"id": 3, "candidateId": 2},
        {"id": 4, "candidateId": 2},
    ]
) == "Jerry"  # One-sided election

# Winner appears later in candidate list
assert solution.winningCandidate(
    [
        {"id": 10, "name": "X"},
        {"id": 20, "name": "Y"},
        {"id": 30, "name": "Z"},
    ],
    [
        {"id": 1, "candidateId": 30},
        {"id": 2, "candidateId": 30},
        {"id": 3, "candidateId": 20},
    ]
) == "Z"  # Correct mapping from ID to name

# Candidates with zero votes
assert solution.winningCandidate(
    [
        {"id": 1, "name": "A"},
        {"id": 2, "name": "B"},
        {"id": 3, "name": "C"},
    ],
    [
        {"id": 1, "candidateId": 1},
        {"id": 2, "candidateId": 1},
    ]
) == "A"  # Unvoted candidates should not affect result

Test Case Summary

Test Why
Problem statement example Validates basic correctness
Single candidate Tests minimum candidate count
Large winning margin Ensures dominant winner is detected correctly
Non-sequential candidate IDs Verifies ID-to-name mapping works properly
Candidates with zero votes Confirms unused candidates do not interfere

Edge Cases

Candidates with zero votes

Some candidates may exist in the Candidate table but never appear in the Vote table. A buggy implementation might accidentally include them with incorrect counts or mishandle missing entries. The solution handles this correctly because vote counts are built only from rows in the Vote table.

Only one candidate exists

If there is only one candidate, every vote necessarily belongs to that candidate. Some implementations incorrectly assume multiple candidates exist and may fail when computing the maximum. The current implementation works naturally because the single candidate becomes the maximum by default.

Non-sequential candidate IDs

Candidate IDs are not guaranteed to be sequential or ordered. A solution that uses array indexing directly could fail or waste memory. The implementation uses hash maps instead, so sparse or irregular IDs are handled correctly.

Very large vote counts

If the Vote table is large, repeatedly scanning it for every candidate becomes inefficient. The optimized solution avoids this issue by processing the votes only once and aggregating counts incrementally.