A scatter-gather query asks every shard for locally sorted candidates, then merges those streams into a global result. Sorting every returned row again wastes work because each shard has already sorted its own output.
Design a CrossShardTopKMerger class:
CrossShardTopKMerger() creates a stateless merger.int[] topK(int[][] shardScores, int k) returns up to the globally greatest k scores in nonincreasing order.
Each row contains one shard's scores in nonincreasing order and may be empty. Equal scores represent distinct results and must not be removed. When k exceeds the total number of scores, return every score.
Example 1:
Input:
Output:
Explanation: The three descending shard streams merge to 10, 9, 8, 7 before any smaller candidate.
Example 2:
Input:
Output:
Explanation: Empty rows are ignored, while the two non-empty shard streams are merged.
Constraints
0 <= shardScores.length <= 10^40 <= total scores <= 10^5- Each row is sorted in nonincreasing order.
0 <= shardScores[i][j] <= 10^90 <= k <= 10^5
Merge Cross-Shard Top-K Resultsmedium