We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Largest Element in a Stream

Difficulty: Easy

Problem Description

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.

Key Insights

  • Use a min-heap to efficiently track the kth largest element.
  • The size of the heap is maintained at k, allowing for quick retrieval of the kth largest element.
  • When adding a new score, compare it with the smallest element in the heap (the root) to determine if it should be included in the top k scores.

Space and Time Complexity

Time Complexity: O(log k) for each add operation due to heap insertion. Space Complexity: O(k) for storing the heap of the top k elements.

Solution

To solve this problem, we can utilize a min-heap (priority queue) to keep track of the k largest elements. When we add a new score, we compare it with the smallest element in the heap. If the new score is larger, we remove the smallest element and add the new score. This way, the root of the min-heap will always be the kth largest element.

Code Solutions

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)  # Add new score to the heap
        if len(self.heap) > self.k:  # Ensure the heap size does not exceed k
            heapq.heappop(self.heap)  # Remove the smallest element
        return self.heap[0]  # The root is the kth largest element
← Back to All Questions