505. Online Election

MediumBinary SearchBinary SearchPrefix SumDesign

Given the votes cast over time (persons[i] receives a vote at strictly increasing times[i]) and a list of query times, return for each query the person leading the election at that moment. The leader is the person with the most votes so far; ties are broken in favor of the most recent person to reach that vote count. Use prefix leaders plus binary search. The input is JSON {persons, times, queries}. Return the leaders as an array.

Input: JSON {persons, times, queries}.

Output: Array — the leader at each query time.

Examples

Example 1
Input: {"persons":[0,1,1,0,0,1,0],"times":[0,5,10,15,20,25,30],"queries":[3,12,25,15,24,8]}
Output: [0,1,1,0,0,1]
Explanation: Leader at each queried time.

Constraints

Asked by

GoogleBloomberg
Solve this problem in the editor →