Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

911. Online Election

Time: Constructor: $O(n)$, q(t: int): $O(\log n)$

Space: $O(n)$

			


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 = --upper_bound(begin(times), end(times), t);
    return timeToLead[*it];
  }

 private:
  const vector<int> times;
  unordered_map<int, int> timeToLead;
};




			


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) {
      count.merge(persons[i], 1, Integer::sum);
      if (count.get(persons[i]) >= 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<>();
}




			


class TopVotedCandidate:
  def __init__(self, persons: List[int], times: List[int]):
    self.times = times
    self.timeToLead = {}
    count = 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]]