The Top K Elements pattern is used to find the top or bottom K elements in a dataset. This is commonly solved using a min-heap or max-heap depending on the problem.
class Solution {
public List<Integer> findTopKElements(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Step 1: Add elements to the heap
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // Remove the smallest element
}
}
// Step 2: Extract elements from the heap
List<Integer> result = new ArrayList<>(minHeap);
Collections.sort(result, Collections.reverseOrder()); // Optional: Sort in descending order
return result;
}
}O(N log K) – Adding and removing elements from the heap.O(K log K) – Sorting the final list of top K elements.O(N log K).Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: [6, 5]
Explanation:
- Add elements to the heap and maintain its size as K.
- The top K elements are [6, 5].