# 911. Online Election

In an election, the `i`-th vote was cast for `persons[i]` at time `times[i]`.

Now, we would like to implement the following query function: `TopVotedCandidate.q(int t)` will return the number of 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.

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:

```At time 3, the votes are [0], and 0 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.
```

Note:

1. `1 <= persons.length = times.length <= 5000`
2. `0 <= persons[i] <= persons.length`
3. `times` is a strictly increasing array with all elements in `[0, 10^9]`.
4. `TopVotedCandidate.q` is called at most `10000` times per test case.
5. `TopVotedCandidate.q(int t)` is always called with `t >= times[0]`.

#### Here’s my rejected solution

```<?php
class TopVotedCandidate {

public \$dic=[];
public \$r =[];

public \$keys = [];
/**
* @param Integer[] \$persons
* @param Integer[] \$times
*/
function __construct(\$persons, \$times) {
\$max = 0;
\$prev_person = null;
for(\$i = 0; \$i < count(\$times); \$i ++){
\$this->inc(\$persons[\$i]);
arsort(\$this->\$dic);

foreach(\$this->\$dic as \$k=>\$v){
\$max_this_round = \$k;
break;
}
\$person_this_round = \$persons[\$i];

if(\$i > 0){
if(\$max_this_round === \$max){
\$person_this_round = \$prev_person;
}
}
echo \$person_this_round;
\$this->\$r[\$times[\$i]] = \$person_this_round;
\$max = \$max_this_round;
\$prev_person = \$persons[\$i];
}
var_dump(\$this->\$r);
ksort(\$this->\$r);
var_dump(\$this->\$r);
\$this->\$keys = array_keys(\$this->\$r);

}

/**
* @param Integer \$t
* @return Integer
*/
function q(\$t) {
\$k =  \$this->binarySearch(\$t);
return \$this->\$r[\$k];
}

function inc(\$p){
if(isset(\$this->\$dic[\$p])){
\$this->\$dic[\$p] ++;
} else {
\$this->\$dic[\$p] = 1;
}
}

function binarySearch(\$x) {
\$arr =  \$this->\$keys;
\$low = 0;
\$high = count(\$arr) - 1;

while (\$low <= \$high) {

// compute middle index
\$mid = floor((\$low + \$high) / 2);

// element found at mid
if(\$arr[\$low] <= \$x && \$arr[\$mid] >= \$x &&  \$mid - \$low <= 1) {
return \$low;
}

if (\$x < \$arr[\$mid]) {
// search the left side of the array
\$high = \$mid -1;
}
else {
// search the right side of the array
\$low = \$mid + 1;
}
echo "\$low-\$mid-\$high\n";
}

return false;
}
}

/**
* Your TopVotedCandidate object will be instantiated and called as such:
* \$obj = TopVotedCandidate(\$persons, \$times);
* \$ret_1 = \$obj->q(\$t);
*/

?>```

Here are the problems:

• Just like the previous problem, my PHP syntax is wrong,  and the prev problem is accepted.  I didn’t even ever question about the syntax
• And I wasted too much time on debugging, caused by syntax.
• And my modified binary search isn’t working
• And yes, that’s totally a mess

#### Here’s the my accepted solution

```<?php
class TopVotedCandidate {

public \$dic=[];
public \$r =[];

public \$keys = [];
/**
* @param Integer[] \$persons
* @param Integer[] \$times
*/
function __construct(\$persons, \$times) {
\$prev_max = 0;
\$prev_winner = null;

for(\$i = 0; \$i < count(\$times); \$i ++){
\$this->inc(\$persons[\$i]);

arsort(\$this->dic);

reset(\$this->dic);
\$winner = key(\$this->dic);

\$max = \$this->dic[\$winner];
if(\$prev_winner !== null){
if(\$max == \$prev_max){
\$winner = \$prev_winner;
}
}
if(\$this->dic[\$persons[\$i]] == \$this->dic[\$winner]){
\$winner = \$persons[\$i];
}

\$prev_max = max(\$prev_max, \$max);
\$prev_winner = \$winner;
\$this->r[\$times[\$i]] = \$winner;

}
ksort(\$this->r);
\$this->keys = array_keys(\$this->r);

}

/**
* @param Integer \$t
* @return Integer
*/
function q(\$t) {
\$k =  \$this->binarySearch(\$t);
echo "\$t => \$k";
return \$this->r[\$k];
}

function inc(\$p){
if(isset(\$this->dic[\$p])){
\$this->dic[\$p] ++;
} else {
\$this->dic[\$p] = 1;
}
}

// This is a modified binary search, finding the nearest smaller index
// just like floorKey in Java's TreeMap
function binarySearch(\$x) {
\$arr =  \$this->keys;
\$low = 0;
\$high = count(\$arr) - 1;

if(\$x < \$arr[\$low]){
return false;
}

while (\$high >= \$low) {
\$mid = \$low + floor((\$high - \$low) / 2);

if(\$x >= \$arr[\$high]){
return (int) \$arr[\$high];
}

if(\$arr[\$mid] == \$x) {
return (int) \$arr[\$mid];
}

if (\$x < \$arr[\$mid]) {
\$high = \$mid-1;
} else {
\$low = \$mid+1;
}

}
return (int) \$arr[\$low-1];

}
}
?>
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* \$obj = TopVotedCandidate(\$persons, \$times);
* \$ret_1 = \$obj->q(\$t);
*/```

This site uses Akismet to reduce spam. Learn how your comment data is processed.