#911
Online Election
MediumArrayHash TableBinary SearchDesignHash MapArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n + m log n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n + m log n)Space O(n)
The optimal solution uses a single pass to count votes and keeps track of the leader at each time point. This allows us to answer each query in constant time.
⚙️
Algorithm
3 steps- 1Step 1: Create a list to store the leader at each time point.
- 2Step 2: Use a dictionary to count votes and determine the leader as votes are counted.
- 3Step 3: For each query, use binary search to find the last time point less than or equal to t and return the corresponding leader.
solution.py23 lines
1class TopVotedCandidate:
2 def __init__(self, persons, times):
3 self.times = times
4 self.leaders = []
5 count = {}
6 leader = -1
7 max_votes = 0
8 for person in persons:
9 count[person] = count.get(person, 0) + 1
10 if count[person] > max_votes:
11 max_votes = count[person]
12 leader = person
13 self.leaders.append(leader)
14
15 def q(self, t):
16 left, right = 0, len(self.times) - 1
17 while left < right:
18 mid = (left + right + 1) // 2
19 if self.times[mid] <= t:
20 left = mid
21 else:
22 right = mid - 1
23 return self.leaders[left]ℹ
Complexity note: The time complexity is O(n) for preprocessing the votes and O(log n) for each query due to binary search, making it efficient for multiple queries.
- 1Understanding the need for efficient data structures can drastically improve performance.
- 2Binary search helps in quickly locating the relevant time index for queries.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.