Problem Description

The Winning Candidate problem describes an election scenario where you are given a list of votes, and each vote is represented by a string indicating the candidate's name. The task is to determine which candidate received the most votes. If there is a tie (two or more candidates have the highest number of votes), the winner is the candidate whose name comes last in lexicographical (dictionary) order.

• The input is a list of strings votes, where each string is a candidate's name.
• There is always at least one vote.
• If multiple candidates have the same maximum number of votes, return the candidate with the name that is last in lexicographical order.
• Assume there is always at least one winner (the input is non-empty).

Thought Process

The core of this problem is to count how many votes each candidate received, then select the candidate(s) with the most votes. If there is a tie, we need a way to break it—specifically, by picking the candidate whose name is lexicographically last.

The naive (brute-force) approach would be to count the votes for each candidate by iterating over the list for each unique candidate, but this is inefficient. Instead, we can use a hash map (dictionary) to tally votes efficiently in a single pass.

Once we've counted the votes, we need to identify the winner. If several candidates have the same count, we compare their names to find the lexicographically last one.

Solution Approach

Let's break down the steps for solving this problem efficiently:

1. Count votes: Use a hash map (dictionary) to count the number of times each candidate's name appears in the votes list. This allows us to tally votes in O(n) time, where n is the number of votes.
2. Find the maximum: After counting, identify the maximum vote count among all candidates.
3. Handle ties: If multiple candidates have the same highest vote count, iterate through the candidates with that count and select the one whose name is lexicographically last.

We use a hash map for counting because it provides O(1) insertion and lookup, making the solution efficient. For the tie-breaker, comparing strings is straightforward and built-in for all major languages.

Example Walkthrough

Let's consider the following example:

• votes = ["Alice", "Bob", "Alice", "David", "Bob", "Bob", "Alice"]

1. Count votes:
   - Alice: 3
   - Bob: 3
   - David: 1
2. Find maximum: The maximum vote count is 3.
3. Handle ties: Both Alice and Bob have 3 votes. Between "Alice" and "Bob", "Bob" comes later lexicographically.
4. Result: The winner is "Bob".

This step-by-step process ensures we correctly identify the winner, even in the case of a tie.

Time and Space Complexity

Brute-force approach: For each unique candidate, count their votes by iterating over the entire list. If there are k unique candidates and n votes, this is O(k * n) time and O(k) space.

Optimized approach:

• Time Complexity: Counting votes takes O(n), finding the max is O(k), and tie-breaking is O(k), where k is the number of unique candidates. Since k ≤ n, overall time is O(n).
• Space Complexity: O(k) for storing vote counts in the hash map.

Summary

To solve the Winning Candidate problem, we efficiently count votes using a hash map, then select the candidate(s) with the highest count, breaking ties using lexicographical order. This approach is both fast and memory-efficient, and leverages built-in data structures for clarity and simplicity. The solution is elegant because it combines counting and tie-breaking in a single, clear process.

Code Implementation

def winningCandidate(votes):
    from collections import Counter
    counts = Counter(votes)
    max_votes = max(counts.values())
    winners = [name for name, cnt in counts.items() if cnt == max_votes]
    return max(winners)
      

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

std::string winningCandidate(const std::vector<std::string>& votes) {
    std::unordered_map<std::string, int> counts;
    for (const auto& name : votes) {
        counts[name]++;
    }
    int max_votes = 0;
    for (const auto& entry : counts) {
        if (entry.second > max_votes) {
            max_votes = entry.second;
        }
    }
    std::string winner = "";
    for (const auto& entry : counts) {
        if (entry.second == max_votes) {
            if (winner == "" || entry.first > winner) {
                winner = entry.first;
            }
        }
    }
    return winner;
}
      

import java.util.*;

public class Solution {
    public String winningCandidate(String[] votes) {
        HashMap<String, Integer> counts = new HashMap<>();
        for (String name : votes) {
            counts.put(name, counts.getOrDefault(name, 0) + 1);
        }
        int maxVotes = 0;
        for (int cnt : counts.values()) {
            if (cnt > maxVotes) {
                maxVotes = cnt;
            }
        }
        String winner = "";
        for (String name : counts.keySet()) {
            if (counts.get(name) == maxVotes) {
                if (winner.equals("") || name.compareTo(winner) > 0) {
                    winner = name;
                }
            }
        }
        return winner;
    }
}
      

function winningCandidate(votes) {
    const counts = {};
    for (const name of votes) {
        counts[name] = (counts[name] || 0) + 1;
    }
    let maxVotes = 0;
    for (const cnt of Object.values(counts)) {
        if (cnt > maxVotes) maxVotes = cnt;
    }
    let winner = "";
    for (const name in counts) {
        if (counts[name] === maxVotes) {
            if (winner === "" || name > winner) {
                winner = name;
            }
        }
    }
    return winner;
}