1
class TopVotedCandidate {
2
  int[] persons;
3
  int[] times;
4
  int length;
5
  Map<Integer, Integer> voteCount;
6
  Map<Integer, Integer> voteLead;
7

8
  public TopVotedCandidate(int[] persons, int[] times) {
9
    this.persons = persons;
10
    this.times = times;
11
    length = times.length - 1;
12
    int leadCount = 0;
13
    int leadPerson = -1;
14
    voteCount = new HashMap<>();
15
    voteLead = new HashMap<>();
16
    for (int i = 0; i <= length; i++) {
17
      int newCount = voteCount.getOrDefault(persons[i], 0) + 1;
18
      voteCount.put(persons[i], newCount);
19
      if (newCount >= leadCount) {
20
        leadCount = newCount;
21
        leadPerson = persons[i];
22
      }
23
      voteLead.put(times[i], leadPerson);
24
    }
25
  }
26

27
  public int q(int t) {
28
    int leadPerson = -1;
29
    if (voteLead.containsKey(t)) {
30
      leadPerson = voteLead.get(t);
31
    } else if (t < times[0]) {
32
      leadPerson = voteLead.get(times[0]);
33
    } else if (t > times[length]) {
34
      leadPerson = voteLead.get(times[length]);
35
    } else {
36
      int low = 0;
37
      int high = length;
38
      while (low <= high) {
39
        int mid = low + (high - low) / 2;
40
        if (times[mid] > t) high = mid - 1;
41
        else low = mid + 1;
42
      }
43
      leadPerson = voteLead.get(times[high]);
44
    }
45
    return leadPerson;
46
  }
47
}