## Algorithm

Problem Name: 911. Online Election

You are given two integer arrays `persons` and `times`. In an election, the `ith` vote was cast for `persons[i]` at time `times[i]`.

For each query at a time `t`, find the person that was leading the election at time `t`. Votes cast at time `t` will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Implement the `TopVotedCandidate` class:

• `TopVotedCandidate(int[] persons, int[] times)` Initializes the object with the `persons` and `times` arrays.
• `int q(int t)` Returns the number of the person that was leading the election at time `t` according to the mentioned rules.

Example 1:

```Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

Explanation
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // return 0, At time 3, the votes are [0], and 0 is leading.
topVotedCandidate.q(12); // return 1, At time 12, the votes are [0,1,1], and 1 is leading.
topVotedCandidate.q(25); // return 1, At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
topVotedCandidate.q(15); // return 0
topVotedCandidate.q(24); // return 0
topVotedCandidate.q(8); // return 1

```

Constraints:

• `1 <= persons.length <= 5000`
• `times.length == persons.length`
• `0 <= persons[i] < persons.length`
• `0 <= times[i] <= 109`
• `times` is sorted in a strictly increasing order.
• `times[0] <= t <= 109`
• At most `104` calls will be made to `q`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *persons;
int *times;
int sz;
int top_v;          // number of top votes at present
int top_p;          // person who has top votes at present

int idx;            // start index to continue to count
} TopVotedCandidate;

TopVotedCandidate* topVotedCandidateCreate(int* persons, int personsSize, int* times, int timesSize) {
TopVotedCandidate *obj = calloc(1, sizeof(TopVotedCandidate));
//assert(obj);
obj->persons = persons;
obj->times = times;
obj->sz = personsSize;
return obj;
}

int topVotedCandidateQ(TopVotedCandidate* obj, int t) {
int p, v, i, j, m;

while (obj->idx < obj->sz && obj->times[obj->idx] <= t) {
p = obj->persons[obj->idx];
if (obj->top_v <= v) {
obj->top_v = v;
obj->top_p = p;
}
obj->idx ++;
}

i = obj->idx - 1;
while (obj->times[i] > t) {
i --;           // use binary search to optimize
}

}

void topVotedCandidateFree(TopVotedCandidate* obj) {
free(obj);
}
``````
Copy The Code &

Input

cmd
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"] [[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]

Output

cmd
[null, 0, 1, 1, 0, 0, 1]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class TopVotedCandidate {
public:
TopVotedCandidate(vector persons, vector times) {
unordered_mapcount;
for (int i = 0; i < times.size(); ++i) {
count[persons[i]]++;
}
}
}

int q(int t) {
return (--m.upper_bound(t))->second;
}

private:

mapm;
};
``````
Copy The Code &

Input

cmd
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"] [[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]

Output

cmd
[null, 0, 1, 1, 0, 0, 1]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class TopVotedCandidate {

private TreeMap currWinner;

public TopVotedCandidate(int[] persons, int[] times) {
this.currWinner = new TreeMap<>();
Map candidateToVotecount = new HashMap<>();
int currWinningCandidate = -1;
for (int i = 0; i < persons.length; i++) {
int person = persons[i];
int newVoteCount = candidateToVotecount.getOrDefault(person, 0) + 1;
candidateToVotecount.put(person, newVoteCount);
if (currWinningCandidate == -1 || newVoteCount >= candidateToVotecount.get(currWinningCandidate)) {
currWinningCandidate = person;
}
currWinner.put(times[i], currWinningCandidate);
}
}

public int q(int t) {
return this.currWinner.floorEntry(t).getValue();
}
}
``````
Copy The Code &

Input

cmd
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"] [[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]

Output

cmd
[null, 0, 1, 1, 0, 0, 1]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class TopVotedCandidate:

def __init__(self, persons, times):
winner = 0
self.winners = [None] * len(times)
self.times = times
for i, person in enumerate(persons):
winner = person
self.winners[i] = winner

def q(self, t):
return self.winners[bisect.bisect(self.times, t) - 1]
``````
Copy The Code &

Input

cmd
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"] [[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]

Output

cmd
[null, 0, 1, 1, 0, 0, 1]