leetcode-data stream

703. Kth Largest Element in a Stream.py

class KthLargest:
    """
    Binary Search+ Insert
    [2,4,5,8]
    k=3
    add 3 -> [2,3,4,5,8]-->return 4
                  -
    add 4 -> [2,3,4,5,5,8]-->return 5
                    -
    [2,3,4,5,5,8,10]
             -
    [2,3,4,5,5,8,9,10]
               -
    [2,3,4,4,5,5,8,9,10]
                 -
    Heap:
    we only care about largetst top k data in data stream, so we use max heap to maintain top 3 data by far. This works because It is guaranteed that there will be at least k elements in the array when you search for the kth element.

    """
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.nums = sorted(nums)

    def add(self, val: int) -> int:
        ix = bisect.bisect_left(self.nums, val) # O(log n)
        self.nums.insert(ix, val) # O(n)
        return self.nums[-self.k]


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)