Kth Largest Element in a Stream

Microsoft Interview Question

Problem Overview

Difficulty: Easy
LeetCode Pattern: Heap

Implement a class named KthLargest that keeps track of test scores and always tells us the kth highest score after each new submission.

Original Input: 
· k = 2
· nums = [2, 4, 5, 8]

add(1)
· Output = 5
· Reason: 2nd highest score is 5

add(9)
· Output = 8
· Reason: 2nd highest score is 8

---

Step 1: Clarify Requirements

• Can k be negative or zero?

  • No.

• Will the initial nums be sorted?

  • No, it won’t always be sorted.

• Can there be duplicate values?

  • Yes, duplicates are allowed.

---

Step 2: Discuss Approaches

1/ Sort on Add (Suboptimal ⚠️)

• Logic:

  • Append the new value to the list

  • Sort the list in ascending order

  • Return the value at index: len(list) - k

• Big O:

  • Time Complexity: O(n·logn)

  • Space Complexity: O(n)

---

2/ Use Min-Heap (Optimal ✅)

• Logic:

  • Use a min-heap of size k

  • Add the incoming value to this heap

  • If heap size > k:

    • Remove the smallest value

  • kth largest will be the top of heap

• Big O:

  • Time Complexity: O(log k)

  • Space Complexity: O(k)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the stream has duplicates?

  • Our solution still works.

• What if n is large and k is close to n?

  • Eg: n is 1,000 and k = 999

  • Min-heap of size 999 is too big.

  • Instead, find (n-k+1)th smallest.

  • That’s 2nd smallest in this case.

  • So we create a max-heap of size 2.

  • Top of max-heap is the kth largest.