# 911. Online Election

## hashmap + treeMap

T: O(nlogn)

S: O(n)

```
 T: O(n) times to build HashMap and TreeMap, 
 1. TreeMap insert is O(logn), so build TreeMap is O(nlogn)
 2. HashMap insert is O(1), so build TreeMap is O(n)
 
 And Query:
 1. O(logn) to query TreeMap (floorKey())
 2. get(key) is O(1)
```

```java

class TopVotedCandidate {

    private TreeMap<Integer, Integer> timeResult;
    private Map<Integer, Integer> personVoteCount;
    private int curLeader = -1;
    private int curMax = -1;
    public TopVotedCandidate(int[] persons, int[] times) {
        timeResult = new TreeMap<>();
        personVoteCount = new HashMap<>();
        timeResult.put(-1, -1);

        for (int i = 0; i < persons.length; i++) {
            int person = persons[i];
            int votes = personVoteCount.getOrDefault(person, 0)+1;
            personVoteCount.put(person, votes);
            if (votes >= curMax) {
                curMax = votes;
                curLeader = person;
            }
            timeResult.put(times[i], curLeader);
        }
    }
    
    public int q(int t) {
        Integer time = timeResult.floorKey(t);
        if (time  == null) {
            return -1;
        }
        return timeResult.get(time);
    }
}

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


 notice, can't store entire HashMap in timeResult -> for all count info -> this becomes n^2 space!
 but we only need cadidate results


 T: O(n) times to build HashMap and TreeMap, 
 1. TreeMap insert is O(logn), so build TreeMap is O(nlogn)
 2. HashMap insert is O(1), so build TreeMap is O(n)
 
 And Query:
 1. O(logn) to query TreeMap (floorKey())
 2. get(key) is O(1)

 */
```

##

## hashmap + treeMap

T: O(nlogn)

S: O(n)

```java
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
```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

```java
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
 */
```
