Leetcode 703. Kth Largest Element in a Stream

Problem

Design a data structure that tracks the k-th largest element in a continuously growing collection of numbers. Your structure should support two operations:

1. Initialization: Create the tracker with a target position k (where 1 means largest, 2 means second-largest, etc.) and an initial array of numbers
2. Add: Insert a new value into the collection and return the current k-th largest element

The challenge is handling potentially thousands of additions efficiently—resorting the entire collection after each insertion would be too slow.

Requirements

1. Implement a class RollingMaxTracker with:

   • A constructor that accepts k (integer) and nums (array of integers)
   • An add(val) method that inserts val and returns the k-th largest element

2. The k-th largest element means the k-th element in descending sorted order (with 1-indexing)

3. If there are fewer than k elements when add is called, you may return negative infinity or handle it appropriately

4. Handle duplicate values correctly—they count as separate elements

Constraints

• 1 ≤ k ≤ 10,000
• 0 ≤ initial array length ≤ 10,000
• Up to 10,000 calls to add
• -10,000 ≤ element values ≤ 10,000
• Your solution should perform better than O(n log n) per addition where n is the current collection size

Examples

Example 1:

tracker = RollingMaxTracker(3, [4, 5, 8, 2]) tracker.add(3) // returns 4 (3rd largest among [4,5,8,2,3] is 4) tracker.add(5) // returns 5 (3rd largest among [4,5,8,2,3,5] is 5) tracker.add(10) // returns 8 (3rd largest among [4,5,8,2,3,5,10] is 8)

Example 2:

tracker = RollingMaxTracker(1, []) tracker.add(7) // returns 7 (1st largest is always the maximum) tracker.add(3) // returns 7 tracker.add(9) // returns 9

Example 3:

tracker = RollingMaxTracker(2, [0]) tracker.add(-1) // returns -1 (2nd largest among [0, -1] is -1) tracker.add(1) // returns 0 (2nd largest among [0, -1, 1] is 0) tracker.add(0) // returns 0 (2nd largest among [0, -1, 1, 0] is 0)

Hint 1: Optimal Data Structure Think about data structures that efficiently maintain sorted order or find the k-th element. You don't need to track ALL elements in sorted order—only enough to know the k-th largest. What structure lets you quickly find and remove the smallest element?

Hint 2: Size Matters If you only need the k-th largest element, do you need to keep more than k elements? Consider maintaining exactly k elements representing the k largest values seen so far. What happens when a new value is smaller than all k elements versus when it's larger?

Hint 3: Heap Strategy A min-heap of size k is perfect for this problem. The root (minimum) of the heap is always your k-th largest element. When adding a value: if it's larger than the root, remove the root and insert the new value. This keeps the heap at size k with the k largest elements, and the smallest of those k is your answer.

Full Solution `` Explanation:

The key insight is that to find the k-th largest element, we only need to track the k largest elements we've seen so far. We use a min-heap of size k because:

1. Min-heap property: The smallest element is at the root, accessible in O(1)

2. Size constraint: By keeping exactly k elements, the smallest in our heap IS the k-th largest overall

3. Efficient updates: When a new value arrives:

   • If we have fewer than k elements, just add it
   • If we have k elements and the new value is larger than the root, the root is no longer in the top k, so we remove it and add the new value
   • The heap automatically reorganizes to maintain the min-heap property

Time Complexity:

• Initialization: O(n log k) where n is the initial array size
• Each add operation: O(log k) for heap push/pop
• Overall for m additions: O((n + m) log k)

Space Complexity: O(k) - we only store k elements in the heap

This is much more efficient than sorting the entire array after each addition, which would be O(n log n) per operation where n grows with each addition.