:orphan:

Kth Largest Element in a Stream
===============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/kth-largest-element-in-a-stream/

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 ``k``\ :sup:```th``` largest
  element in the pool of test scores so far.

**Example 1:**

.. container:: example-block

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

.. container:: example-block

   | **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 <= 10``\ :sup:```4```
- ``1 <= k <= nums.length + 1``
- ``-10``\ :sup:```4```\ ``<= nums[i] <= 10``\ :sup:```4```
- ``-10``\ :sup:```4```\ ``<= val <= 10``\ :sup:```4```
- At most ``10``\ :sup:```4``` calls will be made to ``add``.

.. highlight:: python

Pattern
-------
Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream

Approaches
----------

.. tab-set::

    .. tab-item:: Min Heap

        **Code**

        .. literalinclude:: ../problems/easy/kth-largest-element-in-a-stream/kth_largest_element_in_a_stream__min_heap.py
            :language: python
            :lines: 16-

        **Test**

        >>> from kth_largest_element_in_a_stream__min_heap import KthLargest
        >>> kl = KthLargest(3, [4, 5, 8, 2])
        >>> kl.add(3)
        4
        >>> kl.add(5)
        5
        >>> kl.add(10)
        5
        >>> kl.add(9)
        8
        >>> kl.add(4)
        8

        .. autoclass:: kth_largest_element_in_a_stream__min_heap.KthLargest
           :members:
           :show-inheritance:
           :undoc-members: