Online Election — LeetCode 911 Python Solution

The 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].

Example

Input

["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]

Output

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

Explanation

TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);

Python solution

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        cnt = Counter()
        self.times = times
        self.wins = []
        cur = 0
        for p in persons:
            cnt[p] += 1
            if cnt[cur] <= cnt[p]:
                cur = p
            self.wins.append(cur)

    def q(self, t: int) -> int:
        i = bisect_right(self.times, t) - 1
        return self.wins[i]


# Your TopVotedCandidate object will be instantiated and called as such:
# obj = TopVotedCandidate(persons, times)
# param_1 = obj.q(t)

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 911. Online Election is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems