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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/911.-online-election.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.