64.Kth Largest Element in a Stream

EasyHeap / Priority Queue · 1/7

Problem

Design a class that tracks the k-th largest element of a growing stream of numbers (the k-th largest in sorted order, so duplicates count separately).

KthLargest(int k, int[] nums) initializes with k and the initial numbers.
int add(int val) appends val to the stream and returns the current k-th largest element.

Examples

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: After add(3) the stream is [2,3,4,5,8]; the 3rd largest is 4.
             After add(5): [2,3,4,5,5,8] -> 5. After add(10): -> 5. After add(9): -> 8. After add(4): -> 8.

Input:  ["KthLargest","add","add","add"]
        [[1,[]],[-3],[-2],[-4]]
Output: [null,-3,-2,-2]
Explanation: With k = 1 we always return the maximum seen so far.

Constraints

0 <= nums.length <= 10^4
1 <= k <= nums.length + 1
-10^4 <= nums[i], val <= 10^4
At most 10^4 calls to add.
It is guaranteed there are at least k elements when add returns.

💡 Key Insight

Only the top k values ever matter; anything smaller than the current k-th largest can never become the answer again. Keep those k values in a min-heap: its root is the smallest of the top k, which is exactly the k-th largest. Each add is one push and at most one pop — O(log k).

Brute Force (Sort on Every Add)

TimeO(n log n) per add, where n is the stream length so far.SpaceO(n)

Intuition

Store everything in a list. On each add, append, sort, and read index size - k.

Algorithm

Constructor: copy nums into a list.
add(val): append val, sort the list ascending.
Return list.get(list.size() - k).

Visualization

k = 3, list = [4,5,8,2]
add(3): [2,3,4,5,8]   size-k = 2 -> 4
add(5): [2,3,4,5,5,8] size-k = 3 -> 5

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class KthLargest {
    private final int k;
    private final List<Integer> list = new ArrayList<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int num : nums) {
            list.add(num);
        }
    }

    public int add(int val) {
        list.add(val);
        Collections.sort(list); // full sort every time
        return list.get(list.size() - k);
    }
}

Complexity

Time: O(n log n) per add, where n is the stream length so far.
Space: O(n) — every element is kept.

Sorted List with Binary Insertion

TimeO(n log n) once for the constructor; O(n) per add because of the element shift.SpaceO(n).

Intuition

The list is already sorted before each add, so re-sorting is wasteful. Binary-search the insertion position and insert there. The search is O(log n), but shifting elements in an ArrayList still costs O(n).

Algorithm

Constructor: copy and sort nums once.
add(val): binary-search the first index whose value >= val; insert there.
Return list.get(list.size() - k).

Visualization

list = [2,4,5,8], add(3)
binary search: lo=0, hi=4 -> insert at index 1
list = [2,3,4,5,8] -> answer index 5-3 = 2 -> 4

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class KthLargest {
    private final int k;
    private final List<Integer> list = new ArrayList<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list);
    }

    public int add(int val) {
        int lo = 0, hi = list.size();
        while (lo < hi) { // first index with list[idx] >= val
            int mid = (lo + hi) >>> 1;
            if (list.get(mid) < val) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        list.add(lo, val); // O(n) shift
        return list.get(list.size() - k);
    }
}

Complexity

Time: O(n log n) once for the constructor; O(n) per add because of the element shift.
Space: O(n).

Min-Heap of Size kOptimal

TimeO(n log k) for the constructor, O(log k) per add.SpaceO(k)

Intuition

Keep a min-heap holding only the k largest values seen so far. When a new value arrives, push it; if the heap grows past k, pop the minimum — that value is now too small to ever be the k-th largest. The heap root is the answer.

Algorithm

Constructor: create a PriorityQueue<Integer> (min-heap); call add logic for every number, trimming to size k.
add(val): offer(val); if size() > k, poll().
Return peek().

Dry Run

k = 3, initial nums = [4,5,8,2] → heap keeps {4,5,8} (2 was popped).

flowchart TD
    S["heap = {4,5,8}"] -->|"add 3: push, size 4, pop 3"| A["heap = {4,5,8}<br/>return 4"]
    A -->|"add 5: push, pop 4"| B["heap = {5,5,8}<br/>return 5"]
    B -->|"add 10: push, pop 5"| C["heap = {5,8,10}<br/>return 5"]
    C -->|"add 9: push, pop 5"| D["heap = {8,9,10}<br/>return 8"]
    D -->|"add 4: push, pop 4"| E["heap = {8,9,10}<br/>return 8"]

Code

java

import java.util.PriorityQueue;

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll(); // drop the smallest: it can never be the k-th largest again
        }
        return minHeap.peek(); // smallest of the top k = k-th largest
    }
}

Complexity

Time: O(n log k) for the constructor, O(log k) per add.
Space: O(k) — the heap never holds more than k + 1 elements.

Complexity Comparison

Approach	Time per add	Space
Sort on Every Add	O(n log n)	O(n)
Sorted List + Binary Insertion	O(n)	O(n)
Min-Heap of Size k	O(log k)	O(k)

Common Pitfalls

Using a max-heap: the k-th largest would then be buried inside the heap, not at the root.
Forgetting that nums may have fewer than k elements initially — do not poll until the size exceeds k, and do not assume the heap is full in the constructor.
Trimming only in add but not in the constructor — leaves extra elements so peek() returns a smaller value.
Deduplicating values: [5,5,8] with k = 2 has 5 as the 2nd largest, so duplicates must stay.