EasyNo. 0703

Kth Largest Element in a Stream — LeetCode 703 Python Solution

Topics
Tree, Design, Binary Search Tree, Binary Tree, Data Stream, Heap (Priority Queue)
On a study list
NeetCode 150
Reading time
3 min

The problem

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

Python solution

PythonSolution
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_q = []
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heappush(self.min_q, val)
        if len(self.min_q) > self.k:
            heappop(self.min_q)
        return self.min_q[0]


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

Complexity

Time
O(n × log k)
Space · auxiliary
O(k)

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 703. Kth Largest Element in a Stream is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 703. Kth Largest Element in a Stream?

LeetCode 703. Kth Largest Element in a Stream is rated Easy on LeetCode.

What is the time complexity of LeetCode 703. Kth Largest Element in a Stream?

The Python solution on this page runs in O(n × log k).

What is the space complexity of LeetCode 703. Kth Largest Element in a Stream?

The Python solution on this page uses O(k) auxiliary space.

What topics does LeetCode 703. Kth Largest Element in a Stream cover?

LeetCode 703. Kth Largest Element in a Stream is tagged Tree, Design, Binary Search Tree, Binary Tree, Data Stream and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.