Domain 2MediumCORE

Winning Candidate

We are given a database scenario involving two tables: Candidates (containing candidate IDs and names) and Votes (recording which candidates received votes). The goal is to identify the 'winning' candidate(s)—those with the highest total vote count.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

574. Winning Candidate

Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 52.7%


Problem Breakdown

We are given a database scenario involving two tables: Candidates (containing candidate IDs and names) and Votes (recording which candidates received votes). The goal is to identify the “winning” candidate(s)—those with the highest total vote count.

Inputs:

  • Two relational structures (Candidate, Vote).
  • Implicitly, we assume valid integer keys for joining.

Outputs:

  • A list of winning candidates (ID and Name) who have received the maximum number of votes compared to all others.

Constraints & Edge Cases:

  1. Ties: If multiple candidates share the highest vote count, should we return one or all? In a robust system design context, returning all winners is safer unless specified otherwise (e.g., “lowest ID wins”). I will handle ties by including all max-vote holders to avoid data loss.
  2. Empty Data: If no votes exist for any candidate, the result should be an empty set or nulls handled gracefully.
  3. Null Values: Ensure we don’t count NULL vote entries as valid votes (standard SQL behavior).

Intuition

A brute-force approach would iterate through every row in the Votes table to manually tally counts for each candidate, then compare them pairwise to find the maximum. This is inefficient (O(N2)O(N^2)) and unnecessary given relational capabilities.

The key insight is aggregation. We don’t need to know individual votes; we only care about totals per candidate. By grouping by candidateId first, we reduce NN rows (votes) into KK groups (candidates). Once aggregated, finding the maximum count becomes a simple sort or window function operation (O(Klog⁡K)O(K \log K)).

In an interview setting, I would explain that while SQL is declarative for this task, implementing it in Python demonstrates understanding of data manipulation logic: Join -> Group By Count -> Filter Max.

Approach

  1. Join: Merge the Candidates and Votes tables on the candidate ID to ensure we only count votes for valid candidates (prevents counting orphaned vote records).
  2. Aggregate: Use a group-by operation (groupby) with .size() or .count() to calculate total votes per candidate. This transforms rows into counts.
  3. Identify Max: Determine the maximum vote count across all groups.
  4. Filter & Sort: Filter for candidates matching that max count and sort by ID (optional, but good practice) before returning results.

This mirrors a SQL query using JOIN, GROUP BY HAVING COUNT(*) = MAX(...). In Python/Pandas, this maps directly to .merge(), .groupby().size(), and filtering logic.

Complexity Analysis

  • Time: O(Nlog⁡K)O(N \log K) where NN is the number of votes (for sorting/grouping) and KK is the number of candidates (K≤NK \le N). The dominant cost is typically the sort or hash aggregation during grouping.
  • Space: O(K+M)O(K + M), where MM is memory for intermediate join results and KK stores unique candidate counts in our groupby object.

Solution

import pandas as pd

def get_winning_candidate(candidates: list[dict], votes: list[dict]) -> list[tuple]:
    """
    Identifies the winning candidate(s) based on vote count.
    
    Args:
        candidates: List of dicts representing 'Candidates' table (id, name).
        votes: List of dicts representing 'Votes' table (candidateId).
        
    Returns:
        List of tuples containing (id, name) for all winners with max votes.
    """
    # Convert lists to DataFrames for efficient tabular operations
    df_candidates = pd.DataFrame(candidates) if candidates else None
    df_votes = pd.DataFrame(votes) if votes else None
    
    # Handle empty input cases gracefully
    if not df_candidates or not df_votes:
        return []

    # Join tables on candidate ID to ensure we only count valid votes for known candidates
    merged_df = pd.merge(df_candidates, df_votes[['candidateId']], 
                          left_on='id', right_on='candidateId', how='left')
    
    # Drop rows where join failed (candidates with no votes) if necessary.
    # However, usually we want to count 0 for candidates without votes?
    # For "Winning Candidate", typically only those who received votes matter or 
    # the schema implies every candidate has at least one vote record in 'Votes'.
    # We will drop rows where no match was found (candidates with 0 votes) 
    # unless they are relevant to tie-breaking. Standard SQL problem usually ignores non-voted candidates for "winner".
    
    merged_df = merged_df.dropna(subset=['candidateId'])

    if len(merged_df) == 0:
        return []

    # Aggregate vote counts per candidate ID
    agg_counts = merged_df.groupby('id').size().reset_index(name='vote_count')
    
    # Find the maximum vote count achieved in this election cycle
    max_votes = agg_counts['vote_count'].max()
    
    # Filter for candidates who received exactly that many votes (handles ties)
    winners = agg_counts[agg_counts['vote_count'] == max_votes]

    return list(zip(winners['id'], winners['name']))

Edge Cases Handled

  • No Votes: If votes is empty, the function returns an empty list immediately.
  • Ties in Vote Count: The logic filters for all candidates matching the maximum vote count (vote_count == max_votes) rather than arbitrarily picking one (e.g., via LIMIT 1), ensuring fairness if multiple winners exist.
  • Missing Candidates: Rows where a candidate ID exists but has no votes are dropped during dropna before aggregation, preventing them from skewing the “winner” status unless they have actual vote records.