k largest elements

JavaView on GFG

Intuition

Find k largest elements in an array. Min-heap of size k.

Algorithm

1Maintain min-heap of size k. For each element: if > heap.top or heap.size < k: add, pop if > k.
2Result = heap contents.

Common Pitfalls

•Min-heap (not max-heap) for efficiency. O(n log k). Or sort descending, take first k.

k largest elements.java

Java

// Approach: Min-heap of size k. For each element > heap top, pop and insert. Heap contains k largest.
// Time: O(n log k) Space: O(k)
class Solution {
    public ArrayList<Integer> kLargest(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : arr) {
            pq.offer(num);
            if (pq.size() > k)
                pq.poll();
        }
        ArrayList<Integer> ans = new ArrayList<>(Collections.nCopies(k, 0));
        while (!pq.isEmpty())
            ans.set(--k, pq.poll());
        return ans;
    }
}

Was this solution helpful?