LC-0703 Easy LeetCode

703. Kth Largest Element in a Stream

Tree Design Binary Search Tree Heap (Priority Queue) Binary Tree Data Stream

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 60% Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream

View full problem on LeetCode

Reading material

Trees & Traversals 18 min Design (Data Structures) 14 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  O(nlogk)
# Space: O(k)

import heapq


class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.__k = k
        self.__min_heap = []
        for n in nums:
            self.add(n)
        

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        heapq.heappush(self.__min_heap, val)
        if len(self.__min_heap) > self.__k:
            heapq.heappop(self.__min_heap)
        return self.__min_heap[0]

Solution from kamyu104/LeetCode-Solutions · MIT