Log inSign up
easyLeetCodeNot Started

Kth Largest Element in a Stream

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

Design a class to maintain and query the k-th largest element from a dynamic incoming stream of numbers.

Implement the KthLargest class: - KthLargest(int k, int[] nums): Initializes the object with the integer k and an initial stream of integers nums. - int add(int val): Appends val to the stream and returns the current k-th largest element.

Example 1 · Example 1: Basic Stream:

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 with k=3, nums=[4, 5, 8, 2].\nMin-Heap retains top 3: [4, 5, 8]. Root is 4.\nadd(3): 3 < 4 (ignored), returns 4.\nadd(5): 5 > 4 (heap becomes [5, 5, 8]), returns 5.\nadd(10): 10 > 5 (heap becomes [5, 8, 10]), returns 5.\nadd(9): 9 > 5 (heap becomes [8, 9, 10]), returns 8.\nadd(4): 4 < 8 (ignored), returns 8.

Constraints:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why a Min-Heap of size K maintains the K-th largest element.
  • Analyze the difference between full sorting vs bounded heap maintenance.
  • Implement the class cleanly across all 4 programming languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Dynamic data stream with continuous queries.
  • Kth largest / Kth smallest query repeatedly called.
  • Memory constraint: storing all elements is wasteful when only top k matter.

Algorithmic Decision Tree:

  • Querying kth largest in a stream -> use Min-Heap of size k.
  • Querying kth smallest in a stream -> use Max-Heap of size k.

Connected Patterns:

Find Median from Data StreamKth Largest Element in an ArrayTop K Frequent Elements

1. Brute Force — Sort Array on Every Add

Intuition

Store all numbers in a dynamic array. In add(val), append val, sort the entire array descending, and return index k - 1.

When to apply: When total add queries are very small (M <= 10).

Algorithm

  1. Step 1: In constructor, initialize array with nums.
  2. Step 2: In add(val), append val to array.
  3. Step 3: Sort array descending.
  4. Step 4: Return element at index k - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class KthLargest {
6private:
7 int k;
8 std::vector<int> stream;
9
10public:
11 KthLargest(int kVal, std::vector<int>& nums) : k(kVal), stream(nums) {}
12
13 int add(int val) {
14 stream.push_back(val);
15 std::sort(stream.begin(), stream.end(), std::greater<int>());
16 return stream[k - 1];
17 }
18};
19
20int main() {
21 std::vector<int> nums = {4, 5, 8, 2};
22 KthLargest kth(3, nums);
23 std::cout << kth.add(3) << "\n"; // 4
24 std::cout << kth.add(5) << "\n"; // 5
25 std::cout << kth.add(10) << "\n"; // 5
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(M * N log N) — Sorting N elements on each of M add calls takes O(M * N log N).
  • Space complexity: O(N) — Stores all N elements in dynamic array.

Why Brute Force Doesn't Scale:

With 104 add operations on an array growing to 2 * 104 elements, total operations reach 104 * (2 * 104 * 14) ~ 2.8 * 109 operations, resulting in TLE.

With k = 100 and 104 additions: Min-Heap performs ~104 * log2(100) ~ 6.6 * 104 operations (< 5ms), compared to ~15 seconds for repeated sorting.

2. Better — Binary Search Insertion in Sorted List

Intuition

Keep the list sorted at all times. Binary search locates insert position in O(log N), then insert into array shifting elements in O(N). Return element at index length - k.

When to apply: When heap is not available and array shifts are tolerable.

Algorithm

  1. Step 1: Sort initial array in ascending order.
  2. Step 2: On add(val), binary search insertion index.
  3. Step 3: Insert val at found index.
  4. Step 4: Return element at index length - k.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class KthLargest {
6private:
7 int k;
8 std::vector<int> stream;
9
10public:
11 KthLargest(int kVal, std::vector<int>& nums) : k(kVal), stream(nums) {
12 std::sort(stream.begin(), stream.end());
13 }
14
15 int add(int val) {
16 auto it = std::lower_bound(stream.begin(), stream.end(), val);
17 stream.insert(it, val);
18 return stream[stream.size() - k];
19 }
20};
21
22int main() {
23 std::vector<int> nums = {4, 5, 8, 2};
24 KthLargest kth(3, nums);
25 std::cout << kth.add(3) << "\n"; // 4
26 std::cout << kth.add(5) << "\n"; // 5
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(M * N) — Binary search takes O(log N) but inserting into array takes O(N) due to element shifting.
  • Space complexity: O(N) — Stores all N stream elements in sorted array.

3. Optimal — Min-Heap of Fixed Size K

Intuition

Keep only the k largest elements in a Min-Heap. The root of this heap is the minimum among the k largest, which is the kth largest overall. Each add pushes val and pops min if size > k.

When to apply: Always for stream Kth largest queries.

Algorithm

  1. Step 1: Initialize Min-Heap and store k.
  2. Step 2: Insert initial nums into heap using add(num).
  3. Step 3: In add(val), push val into Min-Heap.
  4. Step 4: If heap size > k, pop min element.
  5. Step 5: Return minHeap.top().

Interactive Trace for Kth Largest Element in a Stream

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Heap initialized with top 3 elements: [4, 5, 8]
Visual state
Values and pointers at this exact step
tree
Root: 4
4
Left: 5
5
Right: 8
8

Node order shown; add connections to display explicit tree edges.

kth_largest: h1
Check / comparison
4 is the 3rd largest element.
Decision / next transition
Root 4 is the current answer.
Why this step matters

Step 1: Heap initialized with top 3 elements: [4, 5, 8]. Root is 4.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class KthLargest {
6private:
7 int k;
8 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
9
10public:
11 KthLargest(int kVal, std::vector<int>& nums) : k(kVal) {
12 for (int num : nums) {
13 add(num);
14 }
15 }
16
17 int add(int val) {
18 minHeap.push(val);
19 if (minHeap.size() > k) {
20 minHeap.pop();
21 }
22 return minHeap.top();
23 }
24};
25
26int main() {
27 std::vector<int> nums = {4, 5, 8, 2};
28 KthLargest kth(3, nums);
29 std::cout << kth.add(3) << "\n"; // 4
30 std::cout << kth.add(5) << "\n"; // 5
31 std::cout << kth.add(10) << "\n"; // 5
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(log k) per add(), O(N log k) init — Heap maintains at most k elements. Each push and pop takes O(log k).
  • Space complexity: O(k) — Min-Heap stores strictly k elements.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Sort Array on Every AddO(M * N log N)O(N)Append val to array on every add() call and sort entire array descending. Return element at index k-1.Full sort on every addition.
2.Better — Binary Search Insertion in Sorted ListO(M * N)O(N)Maintain sorted list. Binary search insertion point in O(log N), insert in O(N) by shifting elements. Return element at index length - k.Linear shifting on insertion.
3.Optimal — Min-Heap of Fixed Size KOptimalO(M log k)O(k)Maintain Min-Heap of size k containing the k largest elements. The root of the Min-Heap is always the kth largest element.None. Perfectly optimal.

Common Pitfalls & Crucial Edge Cases

Using a Max-Heap instead of a Min-Heap

A Max-Heap requires storing ALL N stream elements and popping k times. A Min-Heap stores only k elements.

Resizing heap beyond k

Allowing the heap to grow to size N degrades each add operation from O(log k) to O(log N) and wastes O(N) space.

Crucial Edge Cases to Validate:

  • Initial array length < k — Constructor receives fewer than k elements; initial calls to add() must populate until size reaches k.
  • Duplicate numbers — Handled naturally; heap keeps exact duplicates so kth largest in sorted order is preserved.
  • Negative values — Min-heap comparator works uniformly across negative and positive integers.
  • k = 1 — The kth largest is simply the running maximum.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the invariant clearly: 'The heap stores the k largest elements seen so far; thus, min-heap root is the kth largest.'
  2. Point out that when incoming value <= min-heap root and heap size is already k, we can early-return the root without pushing and popping.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we use a Min-Heap of size k rather than a Max-Heap to find the kth LARGEST element?

Back to DSA Sheet