Skip to content

911. Online Election

  • Time:
    • Constructor: $O(n)$
    • q(t: int): $O(\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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]]