Loading problem...
You are building a real-time analytics dashboard for a competitive gaming platform that needs to continuously track and display the kth highest score among all players as new scores come in. This metric helps the platform determine dynamic cutoff rankings for qualification rounds, leaderboard tiers, and prize distributions.
Your task is to design a data structure that efficiently maintains a stream of integer scores and supports two operations:
Initialization: Given an integer k representing the rank to track, and an optional initial list of scores nums, initialize the tracker.
Add Score: When a new score val is added to the stream, return the current kth highest score across all scores received so far (including the newly added score).
The kth highest score is defined as the score that would appear at position k when all scores are sorted in descending order. For example, if k = 3 and you have scores [10, 8, 6, 4], the 3rd highest score is 6.
Design and implement the StreamingKthHighestTracker class:
StreamingKthHighestTracker(int k, int[] nums) — Initializes the tracker with the rank parameter k and an initial collection of scores nums. The initial collection may be empty.
int add(int val) — Inserts a new score val into the data stream and returns the kth highest score among all scores tracked so far.
Important Notes:
add call, there will be at least k elements in the stream (including the newly added element).operations = ["StreamingKthHighestTracker", "add", "add", "add", "add", "add"]
arguments = [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]][null, 4, 5, 5, 8, 8]StreamingKthHighestTracker tracker = new StreamingKthHighestTracker(3, [4, 5, 8, 2]); tracker.add(3); // Current scores: [4, 5, 8, 2, 3] → Sorted descending: [8, 5, 4, 3, 2] → 3rd highest = 4 tracker.add(5); // Current scores: [4, 5, 8, 2, 3, 5] → Sorted descending: [8, 5, 5, 4, 3, 2] → 3rd highest = 5 tracker.add(10); // Current scores: [4, 5, 8, 2, 3, 5, 10] → Sorted descending: [10, 8, 5, 5, 4, 3, 2] → 3rd highest = 5 tracker.add(9); // Current scores: [4, 5, 8, 2, 3, 5, 10, 9] → Sorted descending: [10, 9, 8, 5, 5, 4, 3, 2] → 3rd highest = 8 tracker.add(4); // Current scores: [4, 5, 8, 2, 3, 5, 10, 9, 4] → Sorted descending: [10, 9, 8, 5, 5, 4, 4, 3, 2] → 3rd highest = 8
operations = ["StreamingKthHighestTracker", "add", "add", "add", "add"]
arguments = [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]][null, 7, 7, 7, 8]StreamingKthHighestTracker tracker = new StreamingKthHighestTracker(4, [7, 7, 7, 7, 8, 3]); tracker.add(2); // Current scores: [7, 7, 7, 7, 8, 3, 2] → Sorted descending: [8, 7, 7, 7, 7, 3, 2] → 4th highest = 7 tracker.add(10); // Current scores: [7, 7, 7, 7, 8, 3, 2, 10] → Sorted descending: [10, 8, 7, 7, 7, 7, 3, 2] → 4th highest = 7 tracker.add(9); // Current scores: [7, 7, 7, 7, 8, 3, 2, 10, 9] → Sorted descending: [10, 9, 8, 7, 7, 7, 7, 3, 2] → 4th highest = 7 tracker.add(9); // Current scores: [7, 7, 7, 7, 8, 3, 2, 10, 9, 9] → Sorted descending: [10, 9, 9, 8, 7, 7, 7, 7, 3, 2] → 4th highest = 8
operations = ["StreamingKthHighestTracker", "add", "add", "add", "add", "add"]
arguments = [[1, []], [1], [2], [3], [1], [2]][null, 1, 2, 3, 3, 3]StreamingKthHighestTracker tracker = new StreamingKthHighestTracker(1, []); tracker.add(1); // Current scores: [1] → 1st highest = 1 tracker.add(2); // Current scores: [1, 2] → 1st highest = 2 tracker.add(3); // Current scores: [1, 2, 3] → 1st highest = 3 tracker.add(1); // Current scores: [1, 2, 3, 1] → 1st highest = 3 tracker.add(2); // Current scores: [1, 2, 3, 1, 2] → 1st highest = 3
With k = 1, we always track the maximum value in the stream.
Constraints