Skip to main content
CodePeetCodePeet
CodePeet 250

Kth Largest Element in a Stream

EASYProblemSolveExternal Links

Description

Design a class that continuously tracks the kth largest element in a growing stream of numbers.

You need to implement the KthLargest class with two operations:

  • KthLargest(int k, int[] nums) — Initializes the object with the integer k and an initial list of test scores nums.
  • int add(int val) — Adds a new value val to the stream and returns the element that is the kth largest among all elements seen so far.

The kth largest element is the kth element when all elements are sorted in descending order. For example, in [8, 5, 4, 2], the 1st largest is 8, the 2nd largest is 5, the 3rd largest is 4, and the 4th largest is 2.

Note that duplicates are counted separately. In [7, 7, 7], the 1st, 2nd, and 3rd largest are all 7.

Examples

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(3, [4, 5, 8, 2]) — Initialize with k=3 and scores [4, 5, 8, 2]. When sorted descending: [8, 5, 4, 2]. The 3rd largest is 4.
  • add(3) → Stream is now [2, 3, 4, 5, 8]. 3rd largest = 4.
  • add(5) → Stream is now [2, 3, 4, 5, 5, 8]. 3rd largest = 5.
  • add(10) → Stream is now [2, 3, 4, 5, 5, 8, 10]. 3rd largest = 5.
  • add(9) → Stream is now [2, 3, 4, 5, 5, 8, 9, 10]. 3rd largest = 8.
  • add(4) → Stream is now [2, 3, 4, 4, 5, 5, 8, 9, 10]. 3rd largest = 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(4, [7, 7, 7, 7, 8, 3]) — Sorted descending: [8, 7, 7, 7, 7, 3]. The 4th largest is 7.
  • add(2) → 4th largest = 7 (2 is too small to affect the top 4).
  • add(10) → Sorted: [10, 8, 7, 7, 7, 7, 3, 2]. 4th largest = 7.
  • add(9) → Sorted: [10, 9, 8, 7, 7, 7, 7, 3, 2]. 4th largest = 7.
  • add(9) → Sorted: [10, 9, 9, 8, 7, 7, 7, 7, 3, 2]. 4th largest = 8.

Constraints

  • 1 ≤ k ≤ nums.length + 1
  • 0 ≤ nums.length ≤ 10^4
  • -10^4 ≤ nums[i] ≤ 10^4
  • -10^4 ≤ val ≤ 10^4
  • At most 10^4 calls will be made to add

Editorial

Brute Force

Intuition

Imagine you are a teacher maintaining a class leaderboard. Every time a new student submits a test score, you write all scores on a whiteboard, sort them from highest to lowest, and then count down to the kth position to announce the kth highest score.

The simplest approach does exactly this: store all numbers in a list. Every time add is called, append the new number, sort the entire list in descending order, and return the element at index k-1 (the kth largest).

This works correctly but is wasteful. Sorting the entire list every single time means we are repeatedly re-sorting elements that were already in order. If we receive 10,000 add calls, we sort 10,000 times — even though most of the list hasn't changed between calls.

Step-by-Step Explanation

Let's trace through Example 1: k=3, initial nums = [4, 5, 8, 2].

Step 1: Initialize: Store all numbers in a list: [4, 5, 8, 2].

Step 2: add(3). Append 3 → list = [4, 5, 8, 2, 3]. Sort descending → [8, 5, 4, 3, 2]. Return element at index k-1 = 2 → answer is 4.

Step 3: add(5). Append 5 → list = [4, 5, 8, 2, 3, 5]. Sort → [8, 5, 5, 4, 3, 2]. Return index 2 → 5.

Step 4: add(10). Append 10 → list becomes 7 elements. Sort → [10, 8, 5, 5, 4, 3, 2]. Return index 2 → 5.

Step 5: add(9). Append 9 → 8 elements. Sort → [10, 9, 8, 5, 5, 4, 3, 2]. Return index 2 → 8.

Step 6: add(4). Append 4 → 9 elements. Sort → [10, 9, 8, 5, 5, 4, 4, 3, 2]. Return index 2 → 8.

Brute Force — Sort Entire List On Every Add — Watch how the entire list is re-sorted from scratch after each new element is added, even though most elements haven't changed positions.

Algorithm

Constructor:

  1. Store all initial numbers in a list
  2. Store k

add(val):

  1. Append val to the list
  2. Sort the entire list in descending order
  3. Return the element at index k-1

Code

class KthLargest {
private:
    vector<int> nums;
    int k;
    
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        this->nums = nums;
    }
    
    int add(int val) {
        nums.push_back(val);
        // Sort entire list descending on every add call
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};
class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.nums = nums
    
    def add(self, val: int) -> int:
        self.nums.append(val)
        # Sort entire list descending on every add call
        self.nums.sort(reverse=True)
        return self.nums[self.k - 1]
class KthLargest {
    private List<Integer> nums;
    private int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.nums = new ArrayList<>();
        for (int num : nums) {
            this.nums.add(num);
        }
    }
    
    public int add(int val) {
        nums.add(val);
        // Sort entire list descending on every add call
        nums.sort(Collections.reverseOrder());
        return nums.get(k - 1);
    }
}

Complexity Analysis

Time Complexity:

  • Constructor: O(1) — just stores the input.
  • add(): O(m log m) per call, where m is the current total number of elements. Sorting m elements costs O(m log m). Over n calls to add, m grows from the initial size to initial_size + n. Total across all calls: O(n × m log m) where m is up to n + initial_size.

Space Complexity: O(m)

We store all elements ever added. After n add calls on an initial array of size p, we hold p + n elements. No extra data structures are used beyond the list itself.

Why This Approach Is Not Efficient

The brute force sorts the entire list on every add call. With up to 10^4 initial elements and 10^4 add calls, the list grows to ~20,000 elements. Sorting 20,000 elements per call costs O(20000 × log 20000) ≈ 280,000 operations per call. Across 10,000 calls, that is roughly 2.8 billion operations — far too slow.

The root problem is twofold:

  1. We sort elements we don't care about. We only need the kth largest, but we sort the entire list including elements that are far too small to ever be in the top k.

  2. We don't preserve any work between calls. Each sort starts from scratch, throwing away the ordering from the previous call.

Key insight: We only need to know the top k elements at any time. If we maintain exactly k elements in a smart data structure, we can:

  • Instantly know the kth largest (it's the smallest among the top k)
  • Efficiently decide whether a new element belongs in the top k
  • Ignore elements that are too small

A min-heap of size k does exactly this. The smallest element in the heap is the kth largest overall, and insertions cost only O(log k) instead of O(m log m).

Optimal Approach - Min Heap of Size k

Intuition

Imagine you are a talent scout who only cares about the top 3 singers in a competition. You keep a small podium with exactly 3 spots. When a new singer auditions:

  • If the podium isn't full yet (fewer than 3 singers), the new singer goes on the podium directly.
  • If the podium is full, you compare the new singer to the weakest person on the podium (the 3rd best). If the new singer is better, they replace the weakest. If not, they are sent home.

The weakest person on the podium is always the kth best overall.

A min-heap of size k implements this podium perfectly:

  • The heap always contains the k largest elements seen so far.
  • The root (minimum element in the heap) is the kth largest — it is the smallest among the top k.
  • When a new element arrives:
    • If the heap has fewer than k elements, insert it.
    • If the new element is larger than the root, remove the root and insert the new element.
    • If the new element is ≤ the root, ignore it — it cannot be in the top k.
  • The answer is always the root of the heap.

This approach never stores more than k elements, making each operation O(log k) regardless of how many total elements have been seen.

Step-by-Step Explanation

Let's trace Example 1: k=3, initial nums = [4, 5, 8, 2].

Step 1: Initialize the min-heap. Insert initial elements one by one, keeping heap size ≤ k=3.

  • Insert 4 → heap = [4] (size 1 < 3, just insert)
  • Insert 5 → heap = [4, 5] (size 2 < 3, just insert)
  • Insert 8 → heap = [4, 5, 8] (size 3 = k, heap is full)
  • Insert 2 → 2 < heap root (4), so 2 is too small for top 3. Discard.
  • Final heap: [4, 5, 8], root = 4.

Step 2: add(3). Compare 3 with heap root 4. 3 < 4, so 3 cannot be in the top 3. Discard. Return root = 4.

Step 3: add(5). Compare 5 with root 4. 5 > 4! Remove 4, insert 5. Heap: [5, 5, 8]. New root = 5. Return 5.

Step 4: add(10). Compare 10 with root 5. 10 > 5! Remove 5, insert 10. Heap: [5, 8, 10]. New root = 5. Return 5.

Step 5: add(9). Compare 9 with root 5. 9 > 5! Remove 5, insert 9. Heap: [8, 9, 10]. New root = 8. Return 8.

Step 6: add(4). Compare 4 with root 8. 4 < 8, discard. Return root = 8.

Min Heap of Size k — Maintaining the Top k Elements — Watch how a min-heap of fixed size k=3 efficiently tracks the kth largest element. The root always holds the answer, and small elements are discarded instantly.

Algorithm

Constructor:

  1. Create an empty min-heap
  2. Store k
  3. For each number in the initial array:
    • If heap size < k: insert the number
    • Else if number > heap root: pop the root, insert the number

add(val):

  1. If heap size < k: insert val into the heap
  2. Else if val > heap root: pop the root, insert val
  3. Return the heap root (this is always the kth largest)

Code

class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int k;
    
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (int num : nums) {
            minHeap.push(num);
            // Keep heap size at most k
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
    }
    
    int add(int val) {
        minHeap.push(val);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
        return minHeap.top();
    }
};
import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.min_heap = []
        for num in nums:
            heapq.heappush(self.min_heap, num)
            # Keep heap size at most k
            if len(self.min_heap) > k:
                heapq.heappop(self.min_heap)
    
    def add(self, val: int) -> int:
        heapq.heappush(self.min_heap, val)
        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)
        return self.min_heap[0]
class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            // Keep heap size at most k
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
    }
    
    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

Complexity Analysis

Time Complexity:

  • Constructor: O(p × log k), where p is the initial array size. Each of the p elements is inserted into the heap (O(log k)), and if the heap exceeds size k, we pop the root (O(log k)).
  • add(): O(log k) per call. We insert into a heap of size k (O(log k)) and possibly pop the root (O(log k)). Over n add calls, the total is O(n × log k).

Compare this to the brute force:

  • Brute force add: O(m log m) per call, where m grows up to p + n.
  • Optimal add: O(log k) per call, where k is fixed.

Since k ≤ m and log k ≤ log m, the optimal approach is always at least as fast and typically much faster.

Space Complexity: O(k)

The min-heap stores at most k elements at any time. All elements that are smaller than the kth largest are discarded and never stored. Compare this to the brute force which stores all p + n elements — the heap approach saves significant memory by only keeping what matters.