Kth Largest Element in a Stream

Problem in Plain English

Design a class that starts with an integer k and an initial list of numbers, then reports the kth largest value in the stream after every new arrival. Duplicates count as separate entries rather than distinct values.

Problem Statement

Design a class to find the kth largest element in a stream of numbers, where ranking follows sorted order and not distinct values.

Implement KthLargest(k, nums), which stores k and ingests the initial nums, and int add(val), which appends val to the stream and returns the element that is currently the kth largest.

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.
There will be at least k elements in the stream when asking for the kth element.

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]

The constructor returns null. Initially the largest three entries are [8,5,4]. After arrivals 3,5,10,9,4, the top-three lists are [8,5,4], [8,5,5], [10,8,5], [10,9,8], [10,9,8], giving cutoffs 4,5,5,8,8. Both copies of 5 count.

Example 2

Input: ["KthLargest","add","add","add"] [[1,[]],[-3],[-2],[-4]]
Output: [null,-3,-2,-2]

With k = 1 the class tracks the maximum, moving from -3 to -2 and staying at -2.

Example 3

Input: ["KthLargest","add","add","add"] [[3,[-2,-2]],[-3],[-2],[0]]
Output: [null,-3,-2,-2]

The constructor has only k minus one entries, so no kth value is requested yet. Adding -3 makes [-2,-2,-3], whose third entry is -3. Adding another -2 makes the top three [-2,-2,-2]; adding 0 leaves [0,-2,-2]. Repeated negative values occupy separate ranks.

Intuition

The kth largest is the smallest member of the top k entries, counting duplicates separately. In Example 1, the top three initially are [8,5,4], so the cutoff is 4. A new 3 stays below that cutoff, while a new 5 replaces 4. Once a value falls outside the top k, future arrivals cannot improve its rank, so a streaming solution can discard it permanently.

Approaches

Sort Each Time

Solution Details

Reveal Sort Each Time: intuition, complexity, and code

Intuition

Keeping every arrival in one list makes the kth largest one sort away: append, sort descending, and read index k minus one. Every call re-sorts the whole history, so the cost climbs with each new value.

Step-by-Step Logic

Copy the initial numbers into instance-owned storage; Example 1 starts with [4,5,8,2] and k = 3. The constructor does not need to answer a rank query.
On each add, append the new value and sort all stored entries in descending numeric order. After add(3), the list is [8,5,4,3,2].
Return index k minus one; index 2 is 4 after the first arrival. Never remove duplicates before indexing.
Repeat the same operation for 5,10,9,4. The sorted lists in the trace give 5,5,8,8, so the complete output is [null,4,5,5,8,8].

Why It Works

The constructor copies every initial entry and each add appends exactly one arrival, so the stored list is the entire stream with its multiplicities. Sorting descending places the largest entry at index 0 and the kth at index k minus one. The valid-query guarantee makes that index exist. Reordering the internal copy does not change the stream multiset or mutate the caller's array.

Dry Run

Sort Each Time: variable states at each step
Operation	Appended value	Stored count	Descending list after sort	Index k minus one	Result
constructor	none	4	[4,5,8,2] (not sorted yet)	2 (not read)	null
add(3)	3	5	[8,5,4,3,2]	2	4
add(5)	5	6	[8,5,5,4,3,2]	2	5
add(10)	10	7	[10,8,5,5,4,3,2]	2	5
add(9)	9	8	[10,9,8,5,5,4,3,2]	2	8
add(4)	4	9	[10,9,8,5,5,4,4,3,2]	2	8

Complexity Analysis

Time Complexity

O(s \log(s+1))

Space Complexity

O(s)

Here s is the stream size after this add and n is the initial size. Each add sorts s entries; this is a worst-case bound even when a runtime exploits sorted runs. The constructor copies n entries in O(n+1) time and O(n+1) space. The object retains O(s) entries, and Java/Python sorting may allocate O(s) temporary storage; The JavaScript bound assumes a conventional O(s log(s+1)) numeric comparison sort with at most O(s) auxiliary storage; ECMAScript does not guarantee sort time or workspace. Across m arrivals, summing per-call bounds gives O(m(n+m) log(n+m+1)) time, plus construction.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4
5class KthLargest {6    private int k;7    private List<Integer> stream = new ArrayList<>();8
9    public KthLargest(int k, int[] nums) {10        this.k = k;11        for (int num : nums) {12            stream.add(num);13        }14    }15
16    public int add(int val) {17        stream.add(val);18        stream.sort(Collections.reverseOrder());19        // Duplicates occupy separate positions; descending rank k is index k - 1.20        return stream.get(k - 1);21    }22}

Hints

Hint 1

Values outside the current top k can never become the answer, so there is no need to keep them.

Hint 2

A min-heap of the survivors puts the smallest survivor, which is the kth largest overall, at the root.

Hint 3

Push each arrival and pop the root whenever the heap grows past k entries.

Edge Cases

An empty initial array requires k = 1 under the published bounds; the first arrival is the running maximum.
The initial array may hold k minus one entries. Build normally, but only requested add calls have a valid kth result.
For k = 1, retain the maximum, even when all values are negative.
Duplicates count separately: three copies of -2 make the third largest -2.
An arrival equal to or below the current root can be inserted then evicted without changing the answer.

Common Mistakes and Interview Tips

Using a max-heap capped at k: removing its root discards the best entry instead of the worst survivor.
Using a set to eliminate duplicates changes the ranking required by the question.
Returning a constructor-time root as a kth answer before k entries exist; construction does not request an answer.
Removing when size equals k leaves only k minus one survivors; trim only on size greater than k.
Sorting the caller's nums array in place creates unexpected mutation; the sorting approach must copy it.
Claiming strict O(log k) for every dynamic-array insertion overlooks occasional O(k) resizing and the k = 1 boundary.

Key Takeaway

For the kth largest of a stream, cap a min-heap at k entries so the root always marks the cutoff between the top k and everything beneath.