Online Election - Practice Coding Problems

Online Election - Problem

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.

Input & Output

Example 1 — Basic Election Tracking

$ 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]

💡 Note: At time 3: person 0 leads (1-0). At time 12: person 1 leads (2-1). At time 25: person 1 leads (3-3, but person 1 voted most recently). At time 15: person 0 leads (2-2, but person 0 voted most recently at time 15).

Example 2 — Early Query

$ Input: persons = [0,1,1,0], times = [0,5,10,15], queries = [2,8]

› Output: [0,1]

💡 Note: At time 2: only person 0 has voted. At time 8: person 1 leads 2-1.

Example 3 — Tie Breaking

$ Input: persons = [0,1,0,1], times = [0,5,10,15], queries = [10,15]

› Output: [0,1]

💡 Note: At time 10: tie 2-2, person 0 voted most recently at time 10. At time 15: tie 2-2, person 1 voted most recently at time 15.

Constraints

1 ≤ persons.length ≤ 5000
times.length == persons.length
0 ≤ persons[i] ≤ 999
1 ≤ times[i] ≤ 10⁹
times is sorted in a strictly increasing order
1 ≤ queries.length ≤ 10⁴
1 ≤ queries[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Vote sequence with persons and times

Process

Track leader changes as votes come in

Query

Find leader at specific query times

Key Takeaway

🎯 Key Insight: Precompute leadership changes and binary search for efficient query answering

Asked in

G Google 15 F Facebook 12 M Microsoft 8

The key insight is to preprocess the election state after each vote, then use binary search for fast query answering. The optimal approach precomputes the leader after each vote (handling tie-breaking by recency), then uses binary search to find the latest vote time ≤ query time. Time: O(N + Q log N), Space: O(N).

Common Approaches

Approach	Time	Space	Notes
✓ Precompute Winners + Binary Search	O(N + Q log N)	O(N)	Precompute the leader at each vote time, then binary search for queries
Brute Force Query Processing	O(Q × N)	O(P)	For each query, count all votes up to that time to find the leader

Precompute Winners + Binary Search — Algorithm Steps

Precompute leader after each vote chronologically
Store (time, leader) pairs
For each query, binary search for latest time ≤ query time
Return the corresponding precomputed leader

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Calculate leader after each vote

Binary Search

Find latest vote time ≤ query time

Return

Get precomputed leader at that time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10000
#define MAX_PERSONS 5000

int binarySearch(int* times, int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (times[mid] <= target) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int* solution(int* persons, int personsSize, int* times, int timesSize, int* queries, int queriesSize, int* returnSize) {
    int* leaders = (int*)malloc(personsSize * sizeof(int));
    int voteCounts[MAX_PERSONS] = {0};
    int currentLeader = persons[0];
    
    // Precompute leader after each vote
    for (int i = 0; i < personsSize; i++) {
        int person = persons[i];
        voteCounts[person]++;
        
        // Update leader (ties broken by most recent vote)
        if (voteCounts[person] >= voteCounts[currentLeader]) {
            currentLeader = person;
        }
        
        leaders[i] = currentLeader;
    }
    
    int* results = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int queryTime = queries[q];
        
        // Binary search for latest time <= queryTime
        int idx = binarySearch(times, timesSize, queryTime);
        
        if (idx >= 0) {
            results[q] = leaders[idx];
        } else {
            results[q] = persons[0]; // No votes yet
        }
    }
    
    free(leaders);
    return results;
}

int main() {
    // Simple parsing for demo - in practice would need robust JSON parsing
    int persons[] = {0, 1, 1, 0, 0, 1, 0};
    int times[] = {0, 5, 10, 15, 20, 25, 30};
    int queries[] = {3, 12, 25, 15, 24, 8};
    
    int returnSize;
    int* result = solution(persons, 7, times, 7, queries, 6, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(N + Q log N)

N votes to precompute leaders, Q queries with log N binary search each

⚡ Linearithmic

Space Complexity

O(N)

Arrays to store precomputed leaders and vote counts

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

1.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Precompute Winners + Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler