# Kth Largest Element in a Stream
**Difficulty:** EASY
[External](https://leetcode.com/problems/kth-largest-element-in-a-stream)
Canonical: https://scaleengineer.com/dsa/problems/kth-largest-element-in-a-stream
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Heap (Priority Queue), Tree, Binary Tree, Binary Search Tree
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Box](https://scaleengineer.com/companies/box), [Tinder](https://scaleengineer.com/companies/tinder)
---
## 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 `k`th highest test score **after** a new score has been submitted. More specifically, we are looking for the `k`th 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.

**Example 1:**

**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

**Example 2:**

**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`.

# Approaches
## Brute Force: Sorting on Every Addition
This approach uses a dynamic list to store all the numbers from the stream. Each time a new number is added via the `add` method, the entire list is sorted to find the `k`th largest element. While simple to conceptualize and implement, its performance degrades quickly as the stream size increases.
**Time:** O(L log L) for each `add` call, where L is the current size of the list. The constructor takes O(1) if we don't sort initially, or O(I log I) if we do (where I is the initial number of elements). The dominant cost comes from repeatedly sorting in the `add` method. · **Space:** O(N), where N is the total number of elements in the stream. We need to store every number that has been added.
**Pros:** Very simple to understand and implement.; Requires minimal data structure knowledge.
**Cons:** Highly inefficient due to re-sorting the entire list on every `add` operation.; Poor scalability as the number of elements in the stream grows.
### Explanation
The core idea is to maintain a collection of all numbers encountered so far. When a new number arrives, we add it to our collection and then sort the entire collection to re-establish order. Once sorted, finding the `k`th largest element is a simple matter of accessing the correct index from the end of the sorted list.

For example, if we have the numbers `[4, 5, 8, 2]` and `k=3`, and we add `3`, our list becomes `[4, 5, 8, 2, 3]`. Sorting this gives `[2, 3, 4, 5, 8]`. The 3rd largest element is at index `5 - 3 = 2`, which is `4`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class KthLargest {
    private int k;
    private List<Integer> stream;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.stream = new ArrayList<>();
        for (int num : nums) {
            this.stream.add(num);
        }
    }

    public int add(int val) {
        this.stream.add(val);
        Collections.sort(this.stream);
        return this.stream.get(this.stream.size() - k);
    }
}
```
### Algorithm
- **Initialization (`KthLargest(k, nums)`):**
  - Store the integer `k`.
  - Create a dynamic list (e.g., `ArrayList` in Java).
  - Add all elements from the initial `nums` array into this list.
- **Adding an element (`add(val)`):**
  - Add the new value `val` to the list.
  - Sort the entire list in ascending order.
  - The `k`th largest element is located at index `list.size() - k`.
  - Return the element at this index.

## Optimized Brute Force: Maintaining a Sorted List
This approach is an improvement over the first one. Instead of re-sorting the entire list every time, we maintain a sorted list. When a new element is added, we find its correct sorted position and insert it there. This avoids a full sort but still requires shifting elements, leading to linear time complexity for each addition.
**Time:** O(L) for each `add` call, where L is the current size of the list. The constructor takes O(I log I) to perform the initial sort on I elements. This is better than the brute-force approach but still not optimal for a large number of `add` calls. · **Space:** O(N), where N is the total number of elements in the stream. All numbers are stored in the list.
**Pros:** More efficient than the full sorting approach, improving `add` from O(L log L) to O(L).; Still relatively easy to implement.
**Cons:** The `add` operation is still slow with a linear time complexity.; Space complexity is O(N), as all elements are stored, which is not optimal.
### Explanation
We start by sorting the initial array of numbers. When a new number `val` is added, we don't re-sort everything. Instead, we find the index where `val` should be inserted to keep the list sorted. While finding this index can be done efficiently in `O(log L)` time using binary search, the insertion into an `ArrayList` at a specific index takes `O(L)` time because all subsequent elements must be shifted one position to the right. After insertion, the `k`th largest element is found at the same `list.size() - k` index.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class KthLargest {
    private int k;
    private List<Integer> stream;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.stream = new ArrayList<>();
        for (int num : nums) {
            this.stream.add(num);
        }
        Collections.sort(this.stream);
    }

    public int add(int val) {
        // A simple linear scan to find the insertion point.
        // A binary search would be faster to find the index, but the
        // list.add(index, value) operation is the O(L) bottleneck.
        int i = 0;
        while (i < stream.size() && stream.get(i) < val) {
            i++;
        }
        stream.add(i, val);
        
        return stream.get(stream.size() - k);
    }
}
```
### Algorithm
- **Initialization (`KthLargest(k, nums)`):**
  - Store the integer `k`.
  - Create a dynamic list and populate it with elements from `nums`.
  - Sort the list once.
- **Adding an element (`add(val)`):**
  - Find the correct position to insert `val` into the sorted list to maintain its order. This can be done with a linear scan or binary search.
  - Insert `val` at that position. This operation takes linear time in an array-based list as it requires shifting elements.
  - Return the element at index `list.size() - k`.

## Optimal Approach: Min-Heap
The most efficient solution involves using a min-heap of a fixed size `k`. The heap stores the `k` largest elements encountered so far. The smallest of these `k` elements (which is the root of the min-heap) is the `k`th largest element in the entire stream. This approach provides optimal time and space complexity.
**Time:** O(log k) for each `add` call. Heap operations (offer, poll, peek) on a heap of size `k` take logarithmic time. The constructor takes O(N log k) to process the initial N elements. · **Space:** O(k). The heap stores at most `k` elements, regardless of the total number of elements in the stream.
**Pros:** Optimal time complexity for adding elements.; Optimal space complexity, as it only stores `k` elements.; Highly scalable for large streams of data.
**Cons:** Slightly more complex to understand if not familiar with the heap data structure.
### Explanation
The key insight is that we only need to keep track of the `k` largest numbers, not all of them. A min-heap is perfect for this. It's a priority queue that always keeps the smallest element at the root. By maintaining a min-heap of size `k`, the root will always be the `k`th largest element seen so far.

When we add a new element `val`:
1. If the heap isn't full (size < `k`), we add `val`.
2. If the heap is full, we check if `val` is larger than the current `k`th largest element (`heap.peek()`). If it is, `val` deserves to be in our set of `k` largest numbers. We remove the smallest member of this set (`heap.poll()`) and add `val`. Otherwise, `val` is smaller than the current `k`th largest, so we can ignore it.

After this process, the root of the heap (`heap.peek()`) is the answer.

```java
import java.util.PriorityQueue;

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> minHeap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        for (int num : nums) {
            // Use the add method's logic to build the initial heap
            add(num);
        }
    }

    public int add(int val) {
        if (minHeap.size() < k) {
            minHeap.offer(val);
        } else if (val > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(val);
        }
        return minHeap.peek();
    }
}
```
### Algorithm
- **Data Structure:** Use a Min-Heap (Priority Queue in Java) to store the `k` largest elements.
- **Initialization (`KthLargest(k, nums)`):**
  - Store `k`.
  - Initialize an empty min-heap.
  - Iterate through the initial `nums` array and call the `add` method for each number to populate the heap correctly.
- **Adding an element (`add(val)`):**
  - If the heap's size is less than `k`, add `val` to the heap.
  - If the heap's size is `k`, compare `val` with the smallest element in the heap (the root, accessible via `peek()`).
  - If `val` is larger than the root, remove the root (`poll()`) and add `val` to the heap (`offer()`).
  - If `val` is smaller or equal, do nothing.
  - The `k`th largest element in the stream is now the root of the min-heap. Return `heap.peek()`.

# Solutions
### Java

```java
class KthLargest { private PriorityQueue < Integer > q ; private int size ; public KthLargest ( int k , int [] nums ) { q = new PriorityQueue <>( k ); size = k ; for ( int num : nums ) { add ( num ); } } public int add ( int val ) { q . offer ( val ); if ( q . size () > size ) { q . poll (); } return q . peek (); } } /** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */
```

### JavaScript

```javascript
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function (
  k,
  nums,
) {
  this.k = k;
  this.heap = new MinHeap();
  for (let num of nums) {
    this.add(num);
  }
};
/** * @param {number} val * @return {number} */ KthLargest.prototype.add =
  function (val) {
    this.heap.offer(val);
    if (this.heap.size() > this.k) {
      this.heap.poll();
    }
    return this.heap.peek();
  };
class MinHeap {
  constructor(data = []) {
    this.data = data;
    this.comparator = (a, b) => a - b;
    this.heapify();
  }
  heapify() {
    if (this.size() < 2) return;
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i);
    }
  }
  peek() {
    if (this.size() === 0) return null;
    return this.data[0];
  }
  offer(value) {
    this.data.push(value);
    this.bubbleUp(this.size() - 1);
  }
  poll() {
    if (this.size() === 0) {
      return null;
    }
    const result = this.data[0];
    const last = this.data.pop();
    if (this.size() !== 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return result;
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = (index - 1) >> 1;
      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }
  bubbleDown(index) {
    const lastIndex = this.size() - 1;
    while (true) {
      const leftIndex = index * 2 + 1;
      const rightIndex = index * 2 + 2;
      let findIndex = index;
      if (
        leftIndex <= lastIndex &&
        this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
      ) {
        findIndex = leftIndex;
      }
      if (
        rightIndex <= lastIndex &&
        this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
      ) {
        findIndex = rightIndex;
      }
      if (index !== findIndex) {
        this.swap(index, findIndex);
        index = findIndex;
      } else {
        break;
      }
    }
  }
  swap(index1, index2) {
    [this.data[index1], this.data[index2]] = [
      this.data[index2],
      this.data[index1],
    ];
  }
  size() {
    return this.data.length;
  }
} /** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */

```

### CPP

```cpp
class KthLargest { public: priority_queue < int , vector < int > , greater < int >> q ; int size ; KthLargest ( int k , vector < int >& nums ) { size = k ; for ( int num : nums ) add ( num ); } int add ( int val ) { q . push ( val ); if ( q . size () > size ) q . pop (); return q . top (); } }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */
```

### Python

```python
class KthLargest : def __init__ ( self , k : int , nums : List [ int ]): self . q = [] self . size = k for num in nums : self . add ( num ) def add ( self , val : int ) -> int : heappush ( self . q , val ) if len ( self . q ) > self . size : heappop ( self . q ) return self . q [ 0 ] # Your KthLargest object will be instantiated and called as such: # obj = KthLargest(k, nums) # param_1 = obj.add(val)
```