## Introduction

This problem is based on one of the famous topics of Data Structures and Algorithms. I.e., HashTable and Binary Search. The hashtable class implements the hashtable, which maps keys to values. Hashtable contains unique values, and null values are not allowed. Java Hashtable class is synchronized.

Binary search is a searching technique used to search in the sorted elements in O(logn) time.

Online Election is a problem where we have to find the number of people leading in votes at a particular time.

We will see different approaches to solving this problem.

Let's move on to our problem statement.

## Problem Statement

We are given two integer arrays persons and times. Elections are going on in the city where the ith vote is cast for the person[i] at times[i].

Now for each query at time t, find the leading candidate in the election at time t.

**Note:**

- In the case of a tie, the most recent vote wins.

Two methods will be implemented one will be for initializing and the other for the query.

Let's understand this problem more clearly with the help of an example, as it is a little confusing.,

["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]]

The first list is the query. Now we have a list of lists. The very first list is a list of persons voted and the second list is the time of voting.

[0,1,1, 0, 0, 1, 0]

[0,5,10,15,20,25,30]

This means at time t=0, a vote was cast for person 0, and at time t=5, one vote was cast for person 1, and so on.

Does the question say that we have to ask who the leading candidate is at t=11 or t=13 or t=2?.

I hope this clears the question as it did for me.

Now let's take t=11.

Now, t=11 is not on the list of times. It falls between t=10 and t=15.

Proposition: If it is not present in times, then the leading candidate at t will be the same candidate who has been leading at time t' where t' < t and t' is the largest element in times that satisfies the inequality.

Proof: Say t= 11. Now we know that 11 is not in time. The largest number smaller than 11 in times is 10. Till 10 person 1 is leading[0,1,1]. Person 1 will lead in 11 as well because the next voting occurs at t=15. Person 1 will keep leading at times 10,11,12,13,14 and may start trailing as the vote is cast at t=15.

So when given a time t, our job becomes first to find the time t'. As time is constantly increasing, we use the binary search here.