LC-0911 Medium LeetCode

911. Online Election

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 52% Topics: Array, Hash Table, Binary Search, Design

Reading material

Arrays & Hashing 12 min Binary Search 12 min Design (Data Structures) 14 min

Reference solution (spoiler · python)

# Time:  ctor: O(n)
#        q:    O(logn)
# Space: O(n)

import collections
import itertools
import bisect


class TopVotedCandidate(object):

    def __init__(self, persons, times):
        """
        :type persons: List[int]
        :type times: List[int]
        """
        lead = -1
        self.__lookup, count = [], collections.defaultdict(int)
        for t, p in itertools.izip(times, persons):
            count[p] += 1
            if count[p] >= count[lead]:
                lead = p
                self.__lookup.append((t, lead))

    def q(self, t):
        """
        :type t: int
        :rtype: int
        """
        return self.__lookup[bisect.bisect(self.__lookup,
                                           (t, float("inf")))-1][1]

Solution from kamyu104/LeetCode-Solutions · MIT