Kth Largest Element in a Stream

LeetCode 703, Easy. Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 13 parametrized pytest cases, and a playground notebook:

lcpy gen -n 703   # by problem number
lcpy gen -s kth_largest_element_in_a_stream   # by problem name

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. You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores. Implement the KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.

Examples

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

Input
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
Output
[null, 7, 7, 7, 8]

Explanation
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2);   // return 7
kthLargest.add(10);  // return 7
kthLargest.add(9);   // return 7
kthLargest.add(9);   // return 8

Constraints

0 <= nums.length <= 104
1 <= k <= nums.length + 1
-104 <= nums[i] <= 104
-104 <= val <= 104
At most 104 calls will be made to add.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

import heapq


class KthLargest:
    # Time: O(n log k) init, O(log k) per add
    # Space: O(k)
    def __init__(self, k: int, nums: list[int]) -> None:
        self.k = k
        self.min_heap: list[int] = []
        for num in nums:
            self.add(num)

    # Time: O(log k)
    # Space: O(k)
    def add(self, val: int) -> int:
        heapq.heappush(self.min_heap, val)
        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)
        # kth largest is the smallest among the k largest elements
        return self.min_heap[0]

Complexity

Time	Space
O(n log k) init, O(log k) per add	O(k)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Kth Largest Element in a Stream

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags