Problem Description

The Online Election problem involves designing a data structure that can efficiently determine the leading candidate at any given time during an election. You are given two lists:

• persons: a list of candidate IDs (integers) representing the person who received the i-th vote.
• times: a list of strictly increasing timestamps (integers), where times[i] is the time the i-th vote was cast.

• A constructor that takes persons and times as input.
• A method q(t) that, given a time t, returns the candidate who was leading the election at time t. If there is a tie, the most recent vote among the tied candidates wins.

Constraints:

• There is exactly one winner at all times (ties are broken by recency).
• Votes are cast in strictly increasing order of time.
• Each q(t) query is for a time t such that t is at least as large as the first vote's time and at most as large as the last vote's time.

Thought Process

At first glance, the problem seems to require, for each query at time t, counting all votes up to that time and finding the candidate with the most votes. However, this brute-force approach would be inefficient, especially if there are many queries or votes.

To optimize, we can observe that votes only change the leader at specific times — namely, when a vote is cast. Thus, we can preprocess and record the leader at each vote time. Then, for any query time t, we can find the most recent time less than or equal to t and directly return the leader at that time.

This leads to an efficient solution using preprocessing and binary search, instead of recalculating everything for each query.

Solution Approach

Let's break down the solution step by step:

1. Preprocessing:
   • Iterate through the persons and times lists simultaneously.
   • Keep a running tally of votes for each candidate using a hash map (dictionary).
   • Track the current leader and update it whenever a candidate equals or exceeds the leader's vote count (recency breaks ties).
   • Record the leader at each time point in a list.
2. Querying:
   • For a given query time t, use binary search to find the largest index i such that times[i] ≤ t.
   • Return the leader at index i.

Why these choices?

• Using a hash map allows O(1) updates and lookups for vote counts.
• Binary search on the times array gives O(log n) query performance.
• Preprocessing ensures that each query is fast and does not require recounting votes.

Example Walkthrough

Suppose persons = [0,1,1,0,0,1,0] and times = [0,5,10,15,20,25,30].

1. At time 0: Candidate 0 receives a vote (votes: {0:1}), leader is 0.
2. At time 5: Candidate 1 receives a vote (votes: {0:1, 1:1}), leader is 1 (recency wins tie).
3. At time 10: Candidate 1 receives a vote (votes: {0:1, 1:2}), leader is 1.
4. At time 15: Candidate 0 receives a vote (votes: {0:2, 1:2}), leader is 0 (recency).
5. At time 20: Candidate 0 receives a vote (votes: {0:3, 1:2}), leader is 0.
6. At time 25: Candidate 1 receives a vote (votes: {0:3, 1:3}), leader is 1 (recency).
7. At time 30: Candidate 0 receives a vote (votes: {0:4, 1:3}), leader is 0.

Preprocessing records: leaders = [0,1,1,0,0,1,0].

For a query q(25):

• Binary search finds index 5 (time 25).
• Leader at index 5 is 1. So q(25) = 1.

• Binary search finds index 5 (last time ≤ 28 is 25).
• Leader at index 5 is 1. So q(28) = 1.

• Index 6, leader is 0. So q(30) = 0.

Time and Space Complexity

Brute-force approach:

• For each query, count votes up to time t: O(n) per query, O(qn) total for q queries.
• Space: O(n) for storing votes.

• Preprocessing: O(n) time and O(n) space to process votes and leaders.
• Each query: O(log n) time for binary search.
• Space: O(n) for leaders and times arrays.

This makes the optimized approach highly efficient for large numbers of queries.

Summary

The Online Election problem is solved efficiently by preprocessing the leader at each vote time and using binary search to answer queries. This leverages the fact that the leader only changes when a vote is cast, and that queries can be mapped to the most recent vote time. The approach is elegant because it combines hash maps for quick vote tallies and binary search for fast queries, achieving excellent performance for both setup and repeated lookups.

Code Implementation

from bisect import bisect_right
from collections import defaultdict

class TopVotedCandidate:

    def __init__(self, persons, times):
        self.leaders = []
        self.times = times
        counts = defaultdict(int)
        leader = -1
        max_votes = 0

        for p in persons:
            counts[p] += 1
            if counts[p] >= max_votes:
                if p != leader:
                    leader = p
                max_votes = counts[p]
            self.leaders.append(leader)

    def q(self, t):
        # Find the rightmost time <= t
        idx = bisect_right(self.times, t) - 1
        return self.leaders[idx]
      

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

using namespace std;

class TopVotedCandidate {
public:
    vector<int> leaders;
    vector<int> times;
    
    TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
        unordered_map<int, int> counts;
        int leader = -1;
        int max_votes = 0;
        for (int i = 0; i < persons.size(); ++i) {
            int p = persons[i];
            counts[p]++;
            if (counts[p] >= max_votes) {
                if (p != leader) {
                    leader = p;
                }
                max_votes = counts[p];
            }
            leaders.push_back(leader);
        }
    }
    
    int q(int t) {
        auto it = upper_bound(times.begin(), times.end(), t);
        int idx = it - times.begin() - 1;
        return leaders[idx];
    }
};
      

import java.util.*;

class TopVotedCandidate {
    private int[] times;
    private int[] leaders;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.leaders = new int[persons.length];
        Map<Integer, Integer> counts = new HashMap<>();
        int leader = -1;
        int maxVotes = 0;
        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i];
            counts.put(p, counts.getOrDefault(p, 0) + 1);
            if (counts.get(p) >= maxVotes) {
                if (p != leader) {
                    leader = p;
                }
                maxVotes = counts.get(p);
            }
            leaders[i] = leader;
        }
    }

    public int q(int t) {
        int left = 0, right = times.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (times[mid] <= t) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return leaders[left];
    }
}
      

class TopVotedCandidate {
    constructor(persons, times) {
        this.times = times;
        this.leaders = [];
        const counts = new Map();
        let leader = -1;
        let maxVotes = 0;
        for (let i = 0; i < persons.length; ++i) {
            const p = persons[i];
            counts.set(p, (counts.get(p) || 0) + 1);
            if (counts.get(p) >= maxVotes) {
                if (p !== leader) {
                    leader = p;
                }
                maxVotes = counts.get(p);
            }
            this.leaders.push(leader);
        }
    }

    q(t) {
        // Binary search for the rightmost index where times[i] <= t
        let left = 0, right = this.times.length - 1;
        while (left < right) {
            let mid = Math.floor((left + right + 1) / 2);
            if (this.times[mid] <= t) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return this.leaders[left];
    }
}