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.