Online Election

Medium Binary Search Bisect Original on LeetCode

Reported atAtlassian

Online Election is a medium binary search problem solved with the bisect pattern. The best approach, optimal (precompute leaders + binary search), runs in O(n) build, O(log n) per query time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recount for every query) up.

Problem

An election records each vote as it happens: the i-th vote went to candidate persons[i] at time times[i], and the times are strictly increasing.

Implement TopVotedCandidate:

  • TopVotedCandidate(int[] persons, int[] times) stores the votes.
  • int q(int t) returns the candidate who was leading at time t, counting every vote cast at or before t.

The leader is the candidate with the most votes. If several candidates are tied for the most votes, the one who received the most recent of those votes leads.

Examples

Example 1

Input
TopVotedCandidate([2, 1, 1, 2, 2, 0], [0, 4, 9, 15, 20, 30]), q(3), q(4), q(9), q(16), q(40)
Output
2, 1, 1, 2, 2
Why
At time 4 candidates 2 and 1 have one vote each and 1 voted last, so 1 leads. At time 16 they have two each and the latest vote went to 2.

Example 2

Input
TopVotedCandidate([0, 1, 2], [5, 6, 7]), q(5), q(6), q(7), q(100)
Output
0, 1, 2, 2
Why
Every candidate has one vote, so the leader is always whoever received the most recent vote.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (recount for every query)O(n) per queryO(n)
Optimal (precompute leaders + binary search)O(n) build, O(log n) per queryO(n)

1Brute force (recount for every query)

TimeO(n) per queryEach query replays up to n votes.
SpaceO(n)The stored votes and one count array of size n.

Keep the raw votes. For each query, replay all votes cast at or before t from scratch, keeping counts and the current leader, and return the leader at the end.

  1. Store persons and times in the constructor.
  2. q(t): reset a count array; for every vote with times[i] <= t, increase its count and make it the leader if its count is at least the leader's count.
  3. Return the leader.
class TopVotedCandidate {
    private final int[] persons, times;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.persons = persons;
        this.times = times;
    }

    public int q(int t) {
        int[] count = new int[persons.length];
        int leader = -1;
        for (int i = 0; i < persons.length && times[i] <= t; i++) {
            int p = persons[i];
            count[p]++;
            if (leader == -1 || count[p] >= count[leader]) leader = p;
        }
        return leader;
    }
}

Edge cases to test

  • A query exactly at a vote time includes that vote
  • A query between two votes uses the state after the earlier one
  • A query after the last vote returns the final leader
  • A tie in vote counts goes to the candidate who received the latest vote, even if the other candidate reached that count first
  • A single vote: every query returns that candidate

Hints

Hint 1

The leader can only change when a vote is cast, so there are at most n different moments to know about.

Hint 2

Walk through the votes once, keeping counts and the current leader. After vote i, the leader is the new candidate if their count is at least the old leader's count (ties go to the latest vote).

Hint 3

Store leader[i] for every vote. A query t needs the last vote with times[i] <= t, which a binary search over times finds in O(log n).

FAQ

What is the best time complexity for Online Election?

Optimal (precompute leaders + binary search) runs in O(n) build, O(log n) per query time and O(n) extra space. The constructor replays the n votes once; every query is one binary search.

Which pattern does Online Election use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.

Is there a brute force solution for Online Election?

Yes. Brute force (recount for every query) takes O(n) per query time and O(n) space. Keep the raw votes.

Which edge cases should I test for Online Election?

A query exactly at a vote time includes that vote; A query between two votes uses the state after the earlier one; A query after the last vote returns the final leader; A tie in vote counts goes to the candidate who received the latest vote, even if the other candidate reached that count first; A single vote: every query returns that candidate.