MEDIUM NC#64 Heap / Priority Queue

703. Kth Largest Element in a Stream

📖 Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Implement KthLargest class: - KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums. - int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Level-order traversal
  • •Queue discipline
  • •Shortest-step interpretation

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply BFS reasoning pattern
  • •Apply Heap reasoning pattern

💡 Approach

  • → Use min heap of size k
  • → Heap always contains k largest elements seen so far
  • → Top of heap is kth largest element
  • → When adding new element, push and maintain heap size
  • → Time: O(n log k) for initialization, O(log k) for add, Space: O(k)

🧭 Prerequisites

#215 Kth Largest Element in an Array #621 Task Scheduler

🛠️ Hints & Pitfalls

Hints

  • •Use min heap of size k
  • •Heap always contains k largest elements seen so far
  • •Top of heap is kth largest element

Common Pitfalls

  • •When adding new element, push and maintain heap size
  • •Time: O(n log k) for initialization, O(log k) for add, Space: O(k)

🧪 Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
(() => { const kthLargest = new KthLargest(3, [4,5,8,2]); return kthLargest.add(3); })();
Expected:
4
Test Case 2
Not run
Input:
(() => { const kthLargest = new KthLargest(3, [4,5,8,2]); kthLargest.add(3); return kthLargest.add(5); })();
Expected:
5
Test Case 3
Not run
Input:
(() => { const kthLargest = new KthLargest(3, [4,5,8,2]); kthLargest.add(3); kthLargest.add(5); return kthLargest.add(10); })();
Expected:
5

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#215 Kth Largest Element in an Array #621 Task Scheduler #973 K Closest Points to Origin #1046 Last Stone Weight
⌘K Search ⌘↩ Run ⌘S Submit