911. Online Election

hashmap + treeMap

T: O(nlogn)

S: O(n)

class TopVotedCandidate {

    private Map<Integer, Integer> votesCountMap;
    private TreeMap<Integer, Integer> timeLeadCandiMap;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.votesCountMap = new HashMap<>();
        this.timeLeadCandiMap = new TreeMap<>();
        int n = persons.length;
        int maxCandi = -1;
        int max = 0;
        for (int i = 0; i < n; i++) {
            votesCountMap.put(persons[i], votesCountMap.getOrDefault(persons[i], 0) + 1);
            if (votesCountMap.get(persons[i]) >= max) {
                maxCandi = persons[i];
                max = votesCountMap.get(persons[i]);
            }
            timeLeadCandiMap.put(times[i], maxCandi);
        }
    }
    
    public int q(int t) {
        Integer floorKey = timeLeadCandiMap.floorKey(t);
        if (floorKey != null) {
            return timeLeadCandiMap.get(floorKey);
        }
        return -1;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);

 [0, 1, 1, 0, 0, 1, 0], 
 
    3
  0.  1  1
 [0, 5, 10, 15, 20, 25, 30]

  max for t

  Map<cadi, count>
 
 time, max

 O(nlogn)
 O(n)

                99
 [0,0,0 ,0,  1],
 [0,6,39,52,75]
 */

hashmap + bs

T: O(nlogn)

S: O(n)

```java
class TopVotedCandidate {
    private record Vote(int time, int leadingCandidate){};
    private Map<Integer, Integer> votesCountMap;
    private List<Vote> leadingVotes = new ArrayList<>();

    public TopVotedCandidate(int[] persons, int[] times) {
        this.votesCountMap = new HashMap<>();
        int n = persons.length;
        int maxCandi = -1;
        int max = 0;
        for (int i = 0; i < n; i++) {
            votesCountMap.put(persons[i], votesCountMap.getOrDefault(persons[i], 0) + 1);
            if (votesCountMap.get(persons[i]) >= max) {
                maxCandi = persons[i];
                max = votesCountMap.get(persons[i]);
            }
            leadingVotes.add(new Vote(times[i], maxCandi));
        }
    }
    private int binarySearch(List<Vote> leadingVotes, int t) {
        int left = 0;
        int right = leadingVotes.size()-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (leadingVotes.get(mid).time == t) {
                return mid;
            } else if (leadingVotes.get(mid).time < t) {
                if (mid + 1 < leadingVotes.size()-1 && leadingVotes.get(mid+1).time > t) {
                    return mid;
                }
                left = mid + 1;
            } else { // time > t
                if (mid - 1 >= 0 && leadingVotes.get(mid-1).time < t) {
                    return mid - 1;
                }
                right = mid - 1;
            }
        }
        // if target search time is bigger than all times, use last one
        return leadingVotes.size()-1;
    }
    public int q(int t) {
        int index = binarySearch(leadingVotes, t);
        return leadingVotes.get(index).leadingCandidate;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);

 [0, 1, 1, 0, 0, 1, 0], 
 
    3
  0.  1  1
 [0, 5, 10, 15, 20, 25, 30]

  max for t

  Map<cadi, count>
 
 time, max

 O(nlogn)
 O(n)

                99
 [0,0,0 ,0,  1],
 [0,6,39,52,75]
 */
```

better structure

class TopVotedCandidate {

    private Map<Integer, Integer> count;
    private int[] maxData;
    private int times[];
    public TopVotedCandidate(int[] persons, int[] times) {
        this.count = new HashMap<>();
        this.times = times;
        this.maxData = new int[persons.length]; // max person in this time
        int max = 0;
        int maxPerson = -1;
        for (int i = 0; i < persons.length; i++) {
            int person = persons[i];
            count.put(person, count.getOrDefault(person, 0) + 1);
            if (count.get(person) >= max) {
                maxData[i] = person;
                maxPerson = person;
                max = count.get(person);
            } else {
                maxData[i] = maxPerson;
            }
        }
        //System.out.println(Arrays.toString(maxData));
    }
    
    public int q(int t) {
        int index = binarySearch(times, t);
        //System.out.println("t:" + t + ", index = " + index);
        return maxData[index];
    }
    private int binarySearch(int[] times, int t) {
        int left = 0;
        int right = times.length-1; // 5
        while (left <= right) {
            int mid = left + (right - left)/2; // 1
            if (times[mid] == t) {
                return mid;
            } else if (times[mid] < t) { // t[1] = 5
                if (mid + 1 < times.length && times[mid+1] > t) {
                    return mid;
                }
                left = mid + 1;
            } else {
                if (mid - 1 >= 0 && times[mid-1] < t) {
                    return mid - 1;
                }
                right = mid - 1; // right = 1
            }
        }
        return times.length-1;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);

 time is sorted
  0.    5      10
 0:1   0:1     0:1
 1:0.  1:1     1:2
 pre:x. pre:0. pre:1

 TreeMap<t, >
 

 bs to find the index in time
 */