Online Election

medium design binary search prefix

Problem

In an election, the i-th vote was cast for persons[i] at time times[i] (times is strictly increasing). Each person leads if they have the most votes so far; ties go to the most recent voter. Build a TopVotedCandidate that answers q(t): who was leading at time t.

Inputpersons = [0, 1, 1, 0, 0], times = [0, 5, 10, 15, 20], q(12)

Output1

By time 12, person 1 has 2 votes vs person 0's 1 vote, so person 1 leads.

persons (comma-separated)

times (comma-separated, increasing)

q(t)

class TopVotedCandidate:
    def __init__(self, persons, times):
        self.times = times
        self.leaders = []
        counts = {}
        leader = -1
        for p in persons:
            counts[p] = counts.get(p, 0) + 1
            if leader == -1 or counts[p] >= counts[leader]:
                leader = p
            self.leaders.append(leader)

    def q(self, t):
        lo, hi = 0, len(self.times)
        while lo < hi:
            mid = (lo + hi) // 2
            if self.times[mid] <= t:
                lo = mid + 1
            else:
                hi = mid
        return self.leaders[lo - 1]

class TopVotedCandidate {
  constructor(persons, times) {
    this.times = times;
    this.leaders = [];
    const counts = new Map();
    let leader = -1;
    for (const p of persons) {
      counts.set(p, (counts.get(p) || 0) + 1);
      if (leader === -1 || counts.get(p) >= counts.get(leader)) leader = p;
      this.leaders.push(leader);
    }
  }
  q(t) {
    let lo = 0, hi = this.times.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.times[mid] <= t) lo = mid + 1;
      else hi = mid;
    }
    return this.leaders[lo - 1];
  }
}

class TopVotedCandidate {
    int[] times, 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;
        for (int i = 0; i < persons.length; i++) {
            int p = persons[i];
            counts.put(p, counts.getOrDefault(p, 0) + 1);
            if (leader == -1 || counts.get(p) >= counts.get(leader)) leader = p;
            leaders[i] = leader;
        }
    }
    public int q(int t) {
        int lo = 0, hi = times.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (times[mid] <= t) lo = mid + 1;
            else hi = mid;
        }
        return leaders[lo - 1];
    }
}

class TopVotedCandidate {
    vector<int> times, leaders;
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
        unordered_map<int, int> counts;
        int leader = -1;
        for (int p : persons) {
            counts[p]++;
            if (leader == -1 || counts[p] >= counts[leader]) leader = p;
            leaders.push_back(leader);
        }
    }
    int q(int t) {
        int lo = 0, hi = times.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (times[mid] <= t) lo = mid + 1;
            else hi = mid;
        }
        return leaders[lo - 1];
    }
};

Explanation

The key insight is that the leader can only change at the moments a vote is cast. So instead of recomputing the winner for every query, we precompute the leader right after each vote once, then answer queries with a quick search.

During the build, we walk the votes in order keeping a running counts map. After tallying each vote we update leader: if the current person now has >= votes compared to the old leader, they become the leader. Using >= (not just >) is what makes ties go to the most recent voter. We store this leader into self.leaders, one entry per vote.

To answer q(t), we binary search the strictly increasing times array for the last vote whose time is at or before t. The loop narrows lo and hi until lo points just past that vote, so the answer is leaders[lo - 1].

Example: persons = [0,1,1,0,0], times = [0,5,10,15,20]. After vote index 2 (time 10), person 1 leads with 2 votes, so leaders[2] = 1. For q(12), the binary search finds index 2 is the last vote at or before 12, and returns leaders[2] = 1.

Building is O(n) and each query is just a binary search, so O(log n).

Time: O(n) build, O(log n) per query Space: O(n)