Kth Largest Element in a Stream

LeetCode 789 | Difficulty: Easy

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 `k^th` 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 <= 10^4`

- `1 <= k <= nums.length + 1`

- `-10^4 <= nums[i] <= 10^4`

- `-10^4 <= val <= 10^4`

- At most `10^4` calls will be made to `add`.

Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream

---

Approach

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

---

Solutions

Solution 1: C# (Best: 300 ms)

Metric	Value
Runtime	300 ms
Memory	52.4 MB
Date	2022-02-05

Solution

public class KthLargest
{
    private SortedDictionary<int, int> minHeap;
    private int kth;
    private int size;

    public KthLargest(int k, int[] nums)
    {
        kth = k;
        minHeap = new SortedDictionary<int, int>();
        foreach (var num in nums)
        {
            Add(num);
        }
    }

    public int Add(int val)
    {
        if(minHeap.ContainsKey(val))
        minHeap[val]++;
        else minHeap.Add(val, 1);
        size++;
        if(size>kth)
        {
            var first = minHeap.First();
            if(first.Value == 1) minHeap.Remove(first.Key);
            else minHeap[first.Key]--;
            size--;
            
        }
        return minHeap.First().Key;
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.Add(val);
 */

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Clarify the expected time complexity for each operation before choosing data structures.