LeetCode 911 - Online Election

The problem is asking us to design a data structure that can efficiently answer queries about the leader of an election at any given time. We are given two integer arrays, persons and times.

leetcodemediumarrayhash-tablebinary-searchdesign

LeetCode Problem 911

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Design

Solution

Problem Understanding

The problem is asking us to design a data structure that can efficiently answer queries about the leader of an election at any given time. We are given two integer arrays, persons and times. The persons array represents the sequence of votes, where persons[i] is the candidate who received the ith vote. The times array represents when each vote occurred, such that times[i] is the time of the ith vote.

For a query at time t, we need to determine which candidate had the most votes at that exact time. If multiple candidates are tied for the highest number of votes, the most recent vote among the tied candidates determines the leader. The solution must support multiple queries efficiently because up to 10,000 calls to q(t) may be made.

The constraints tell us that the input arrays are relatively small (persons.length ≤ 5000) but the number of queries can be large. The times array is strictly increasing, which allows us to efficiently search for the relevant vote count using binary search.

Edge cases to consider include queries that occur before the first vote, queries that occur exactly at a vote time, and cases where multiple candidates are tied in votes but the most recent vote determines the winner.

Approaches

A brute-force solution would evaluate each query by iterating over all votes up to time t and counting the votes for each candidate. While this would give the correct result, it would be inefficient for repeated queries since counting votes for each query takes O(n) time. Given up to 10,000 queries, this approach could result in 50,000,000 operations in the worst case, which is too slow.

The key insight for an optimal solution is that we can precompute the leader after each vote. Once we know the leader at each vote time, any query reduces to a simple search for the most recent vote at or before time t. Since times is sorted, we can use binary search to efficiently find the correct index. Precomputing leaders allows each query to run in O(log n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * q) O(n) Count votes for each query separately
Optimal O(n + q * log n) O(n) Precompute leader array, use binary search for queries

Algorithm Walkthrough

  1. Initialize a dictionary (hash map) vote_count to keep track of the number of votes for each candidate.
  2. Initialize an empty list leaders to store the leader after each vote.
  3. Initialize a variable current_leader to keep track of the candidate with the most votes so far.
  4. Iterate over each vote in the persons array:
  • Increment the vote count for the current candidate in vote_count.
  • If the current candidate's vote count is greater than or equal to the current leader's vote count, update current_leader to the current candidate. This handles ties by giving preference to the most recent vote.
  • Append current_leader to the leaders list.
  1. To answer a query q(t):
  • Use binary search on the times array to find the largest index i such that times[i] ≤ t.
  • Return leaders[i].

Why it works: By precomputing the leader at each vote time and storing it in order, we ensure that any query can be answered by looking up the leader corresponding to the closest vote time at or before the query. The tie-breaking rule is naturally handled by updating the leader whenever a candidate reaches the same vote count as the current leader.

Python Solution

from typing import List
import bisect

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        self.times = times
        self.leaders = []
        self.vote_count = {}
        current_leader = -1
        max_votes = 0

        for i, person in enumerate(persons):
            self.vote_count[person] = self.vote_count.get(person, 0) + 1
            if self.vote_count[person] >= max_votes:
                if person != current_leader:
                    current_leader = person
                max_votes = self.vote_count[person]
            self.leaders.append(current_leader)

    def q(self, t: int) -> int:
        # Find rightmost time <= t using bisect
        index = bisect.bisect_right(self.times, t) - 1
        return self.leaders[index]

The Python implementation maintains a vote count for each candidate, updates the current leader after each vote, and precomputes the leader array. Queries are answered using binary search (bisect_right) to efficiently find the most recent vote at or before the query time.

Go Solution

package main

import "sort"

type TopVotedCandidate struct {
	times   []int
	leaders []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	voteCount := make(map[int]int)
	leaders := make([]int, len(persons))
	currentLeader := -1
	maxVotes := 0

	for i, person := range persons {
		voteCount[person]++
		if voteCount[person] >= maxVotes {
			if person != currentLeader {
				currentLeader = person
			}
			maxVotes = voteCount[person]
		}
		leaders[i] = currentLeader
	}

	return TopVotedCandidate{
		times:   times,
		leaders: leaders,
	}
}

func (this *TopVotedCandidate) Q(t int) int {
	index := sort.Search(len(this.times), func(i int) bool {
		return this.times[i] > t
	})
	return this.leaders[index-1]
}

The Go implementation follows the same logic as Python. It uses sort.Search for binary search, which returns the first index where the condition is true. We subtract 1 to get the largest time less than or equal to t. Maps handle the vote count efficiently, and slices store the leader history.

Worked Examples

For the input persons = [0,1,1,0,0,1,0] and times = [0,5,10,15,20,25,30], the state of the algorithm after each vote is:

i Vote vote_count current_leader leaders
0 0 {0:1} 0 [0]
1 1 {0:1,1:1} 1 [0,1]
2 1 {0:1,1:2} 1 [0,1,1]
3 0 {0:2,1:2} 0 [0,1,1,0]
4 0 {0:3,1:2} 0 [0,1,1,0,0]
5 1 {0:3,1:3} 1 [0,1,1,0,0,1]
6 0 {0:4,1:3} 0 [0,1,1,0,0,1,0]

Query q(12) uses binary search to find index 2 (time 10), returning leaders[2] = 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n + q * log n) Precompute leaders in O(n), each query uses binary search O(log n)
Space O(n) Store leaders array and vote_count dictionary

The reasoning is that computing the vote counts and leader array is linear in the number of votes. Queries are independent and use binary search, making them logarithmic in the number of votes.

Test Cases

# Provided example
obj = TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30])
assert obj.q(3) == 0  # Only first vote counted
assert obj.q(12) == 1 # Votes [0,1,1]
assert obj.q(25) == 1 # Votes [0,1,1,0,0,1]
assert obj.q(15) == 0 # Votes [0,1,1,0]
assert obj.q(24) == 0 # Votes [0,1,1,0,0]
assert obj.q(8) == 1  # Votes [0,1]

# Edge cases
obj = TopVotedCandidate([1], [5])
assert obj.q(5) == 1  # Single vote
assert obj.q(4) == None # t before first vote, optional handling

obj = TopVotedCandidate([0,0,0,0], [1,2,3,4])
assert obj.q(3) == 0  # All votes same candidate
assert obj.q(4) == 0

obj = TopVotedCandidate([0,1,2,1,2,0,1],