911. Online Election LeetCode Solution

In this guide, you will get 911. Online Election LeetCode Solution with the best time and space complexity. The solution to Online Election problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Online Election solution in C++
Online Election solution in Java
Online Election solution in Python
Additional Resources

911. Online Election LeetCode Solution image

Problem Statement of Online Election

You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i].
For each query at a time t, find the person that was leading the election at time t. Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.
Implement the TopVotedCandidate class:

TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
int q(int t) Returns the number of the person that was leading the election at time t according to the mentioned rules.

Example 1:

Input
[“TopVotedCandidate”, “q”, “q”, “q”, “q”, “q”, “q”]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

Explanation
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // return 0, At time 3, the votes are [0], and 0 is leading.
topVotedCandidate.q(12); // return 1, At time 12, the votes are [0,1,1], and 1 is leading.
topVotedCandidate.q(25); // return 1, At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
topVotedCandidate.q(15); // return 0
topVotedCandidate.q(24); // return 0
topVotedCandidate.q(8); // return 1

Constraints:

1 <= persons.length <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 109
times is sorted in a strictly increasing order.
times[0] <= t <= 109
At most 104 calls will be made to q.

Complexity Analysis

Time Complexity: O(\log n)
Space Complexity: O(n)

911. Online Election LeetCode Solution in C++

class TopVotedCandidate {
 public:
  TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
    unordered_map<int, int> count;  // {person: voted}
    int lead = -1;

    for (int i = 0; i < persons.size(); ++i) {
      if (++count[persons[i]] >= count[lead])
        lead = persons[i];
      timeToLead[times[i]] = lead;
    }
  }

  int q(int t) {
    auto it = --ranges::upper_bound(times, t);
    return timeToLead[*it];
  }

 private:
  const vector<int> times;
  unordered_map<int, int> timeToLead;
};
/* code provided by PROGIEZ */

911. Online Election LeetCode Solution in Java

class TopVotedCandidate {
  public TopVotedCandidate(int[] persons, int[] times) {
    this.times = times;
    int lead = -1;
    Map<Integer, Integer> count = new HashMap<>(); // {person: voted}

    for (int i = 0; i < persons.length; ++i) {
      if (count.merge(persons[i], 1, Integer::sum) >= count.getOrDefault(lead, 0))
        lead = persons[i];
      timeToLead.put(times[i], lead);
    }
  }

  public int q(int t) {
    final int i = Arrays.binarySearch(times, t);
    return i < 0 ? timeToLead.get(times[-i - 2]) : timeToLead.get(times[i]);
  }

  private final int[] times;
  private Map<Integer, Integer> timeToLead = new HashMap<>();
}
// code provided by PROGIEZ

911. Online Election LeetCode Solution in Python

class TopVotedCandidate:
  def __init__(self, persons: list[int], times: list[int]):
    self.times = times
    self.timeToLead = {}
    count = collections.Counter()  # {person: voted}
    lead = -1

    for person, time in zip(persons, times):
      count[person] += 1
      if count[person] >= count[lead]:
        lead = person
      self.timeToLead[time] = lead

  def q(self, t: int) -> int:
    i = bisect_right(self.times, t)
    return self.timeToLead[self.times[i - 1]]
 # code by PROGIEZ