Online Election

Medium
2060.

Online Election

Online Election is a medium coding problem on arrays, hash table and binary search, asked in Google interviews.

An election records its votes as they arrive: the i-th vote went to candidate persons[i] at time times[i], and the times are strictly increasing.

Write the class TopVotedCandidate:

  • TopVotedCandidate(int[] persons, int[] times) stores the votes.
  • int q(int t) returns the candidate who was leading at time t — the one with the most votes among the votes cast at or before t. A vote cast exactly at t counts. If several candidates are tied for the most votes, the one among them who received a vote most recently leads.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["TopVotedCandidate","q","q","q","q","q"] [[[0,1,1,0,0,1],[0,4,9,15,22,30]],[3],[9],[16],[25],[30]]
Output
[null,0,1,0,0,1]
Explanation
By time 3 only candidate 0 has a vote. At time 9 the counts are 0:1, 1:2, so 1 leads. At 16 they are 2:2 and candidate 0 voted last, so 0 leads; at 25 candidate 0 has 3. At 30 it is 3:3 again and the latest vote went to 1.

Example 2

Input
["TopVotedCandidate","q","q"] [[[1,0],[7,8]],[7],[1000000000]]
Output
[null,1,0]
Explanation
Candidate 1 leads at time 7. At time 8 candidate 0 draws level and, having received the latest vote, leads from then on.

Constraints

  • 1 <= persons.length <= 5000
  • times.length == persons.length
  • 0 <= persons[i] < persons.length
  • 0 <= times[i] <= 10^9
  • times is strictly increasing
  • times[0] <= t <= 10^9
  • At most 10^4 calls are made to q
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} persons
 * @param {number[]} times
 */
var TopVotedCandidate = function(persons, times) {
    
};

/**
 * @param {number} t
 * @return {number}
 */
TopVotedCandidate.prototype.q = function(t) {
    
};

Sign in to run your own test cases

Sign in

Online Election — Solution in Python, Java & C++

Online Election solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.

Online Election is a medium coding problem on arrays, hash table and binary search, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Binary Search
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An election records its votes as they arrive: the i-th vote went to candidate persons[i] at time times[i], and the times are strictly increasing.

Write the class TopVotedCandidate:

  • TopVotedCandidate(int[] persons, int[] times) stores the votes.
  • int q(int t) returns the candidate who was leading at time t — the one with the most votes among the votes cast at or before t. A vote cast exactly at t counts. If several candidates are tied for the most votes, the one among them who received a vote most recently leads.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["TopVotedCandidate","q","q","q","q","q"]
[[[0,1,1,0,0,1],[0,4,9,15,22,30]],[3],[9],[16],[25],[30]]
Output: [null,0,1,0,0,1]
Explanation: By time 3 only candidate 0 has a vote. At time 9 the counts are 0:1, 1:2, so 1 leads. At 16 they are 2:2 and candidate 0 voted last, so 0 leads; at 25 candidate 0 has 3. At 30 it is 3:3 again and the latest vote went to 1.

Example 2

Input: ["TopVotedCandidate","q","q"]
[[[1,0],[7,8]],[7],[1000000000]]
Output: [null,1,0]
Explanation: Candidate 1 leads at time 7. At time 8 candidate 0 draws level and, having received the latest vote, leads from then on.

Constraints

  • 1 <= persons.length <= 5000
  • times.length == persons.length
  • 0 <= persons[i] < persons.length
  • 0 <= times[i] <= 10^9
  • times is strictly increasing
  • times[0] <= t <= 10^9
  • At most 10^4 calls are made to q

Hints for Online Election

  1. Hint 1

    The leader only changes when a vote arrives, so there are at most n different answers — one per vote.

  2. Hint 2

    Walk the votes once in time order, keeping a count per candidate and the current leader. After vote i, record who leads.

  3. Hint 3

    A query at time t asks about the last vote cast at or before t: find it with a binary search over times and return the leader recorded there. Ties go to the newest voter, so update the leader when the new count is >= the leader's.

How to solve Online Election

Precompute the leader after every vote, then answer each query by binary searching for the last vote at or before t.

Approach

  1. Scan the votes in order with a count per candidate and a current leader.
  2. After counting vote i for candidate p, if count[p] >= count[leader] then leader = p; store lead[i] = leader.
  3. q(t): binary search the largest i with times[i] <= t (it exists because t >= times[0]) and return lead[i].

Why it works

Between two consecutive votes the counts do not change, so the leader at time t is the leader just after the last vote cast at or before t. During the scan only the candidate who just received a vote can overtake: with >=, a candidate who draws level becomes leader because they are now the most recent voter among the tied ones, which is exactly the tie rule.

Complexity

  • Time — O(n) to build, O(log n) per query
  • Space — O(n)

Pitfalls

  • Using > instead of >= keeps the older candidate on a tie — the rule is the opposite.
  • A vote cast exactly at time t counts; search for the last time <= t, not < t.
  • Recounting the votes for every query is O(n) a query, 5 × 10^7 steps at the limits.

Reference solution

Python

import bisect

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        self.times = times
        self.lead = []
        count = [0] * len(persons)
        leader = persons[0]
        for p in persons:
            count[p] += 1
            if count[p] >= count[leader]:  # a tie goes to the newest voter
                leader = p
            self.lead.append(leader)

    def q(self, t: int) -> int:
        return self.lead[bisect.bisect_right(self.times, t) - 1]

Java

class TopVotedCandidate {
    private int[] times, lead;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        lead = new int[persons.length];
        int[] count = new int[persons.length];
        int leader = persons[0];
        for (int i = 0; i < persons.length; i++) {
            int p = persons[i];
            count[p]++;
            if (count[p] >= count[leader]) leader = p; // a tie goes to the newest voter
            lead[i] = leader;
        }
    }

    public int q(int t) {
        int lo = 0, hi = times.length - 1; // last vote at or before t
        while (lo < hi) {
            int mid = (lo + hi + 1) >>> 1;
            if (times[mid] <= t) lo = mid; else hi = mid - 1;
        }
        return lead[lo];
    }
}

C++

class TopVotedCandidate {
    vector<int> times, lead;
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
        vector<int> count(persons.size(), 0);
        int leader = persons[0];
        for (int p : persons) {
            count[p]++;
            if (count[p] >= count[leader]) leader = p; // a tie goes to the newest voter
            lead.push_back(leader);
        }
    }

    int q(int t) {
        int i = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return lead[i];
    }
};

JavaScript

var TopVotedCandidate = function(persons, times) {
    this.times = times;
    this.lead = [];
    var count = new Array(persons.length).fill(0);
    var leader = persons[0];
    for (var i = 0; i < persons.length; i++) {
        var p = persons[i];
        count[p]++;
        if (count[p] >= count[leader]) leader = p; // a tie goes to the newest voter
        this.lead.push(leader);
    }
};

TopVotedCandidate.prototype.q = function(t) {
    var lo = 0, hi = this.times.length - 1; // last vote at or before t
    while (lo < hi) {
        var mid = (lo + hi + 1) >> 1;
        if (this.times[mid] <= t) lo = mid; else hi = mid - 1;
    }
    return this.lead[lo];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets