# 703. Kth Largest Element in a Stream

--

Leetcode #: 703
Name: Kth Largest Element in a Stream
Difficulty: Easy
Url: https://leetcode.com/problems/kth-largest-element-in-a-stream/

# Prompt

Your task is to design a class that finds the`kth`largest element in a stream. It’s important to note that it is the`kth`largest element in sorted order, not the`kth`distinct element.

The class needs to have 2 components:

1. KthLargest(int k, int[] nums) — initializes the object with the integer k and the stream of integers nums.
2. int add(int val) — appends the integer val to the stream and returns the element representing the kth largest element in the stream.

# Approach

The naive approach for this problem would be to presort the given nums array (stream) by using your coding language’s built-in sorting method. After sorting the nums array (stream), you can find the kth largest element. The time complexity of this algorithm in the worst case would be dominated by the presorting — O(nlogn). Subsequently, the searching of the kth largest element from the presorted nums array (stream) would be O(n). When analyzing asymptotic time complexity, we would say that our algorithm is O(nlogn) as nlogn scales more than n.

A more efficient approach could be accomplished by utilizing a priority queue, specifically a min-heap. We can convert our nums array (stream) into a heap (for Python, we can conveniently convert an array into a heap using heapify). Then we can check that as long as the length of the nums array (stream) is greater than k, we want to pop from our min-heap until the length of the nums array (stream) is equal to k. By having the length of the nums array (stream) equal to k, we can pop the root element from our min-heap, which would be the kth largest element.

According to the constraints of the problem, it is important to note that we are guaranteed that there will be at least `k` elements in the array when you search for the `kth` element. Whenever a test case calls the add method, we need to return the kth largest element as well but this constraint guarantees that when we return the kth largest element by running the add method, we don’t have to worry about running into an error of reading the kth largest element in an array that doesn’t have k elements.