Find the K Largest Elements in an Array

Finding the k largest elements in an array is a classic algorithmic problem frequently asked in coding interviews. It tests your knowledge of data structures, specifically priority queues and heaps. In this comprehensive guide, we will explore the optimal C++ solution to extract the k largest elements in decreasing order.

Understanding the K Largest Elements Problem

Given an array of positive integers and an integer k, the objective is to return the k largest elements from the array, sorted in decreasing order. While a naive approach might involve sorting the entire array in O(N log N) time, we can optimize this significantly using a min-heap, reducing the time complexity to O(N log k).

Example Scenarios

Input: arr[] = [12, 5, 787, 1, 23], k = 2
Output: [787, 23]
Explanation: The first largest element in the array is 787 and the second largest is 23.

Input: arr[] = [1, 23, 12, 9, 30, 2, 50], k = 3 
Output: [50, 30, 23]
Explanation: The three largest elements in the array are 50, 30, and 23.

Problem Constraints

• 1 <= k <= arr.size() <= 10^6
• 1 <= arr[i] <= 10^6

Optimal C++ Solution Using a Min-Heap

To efficiently track the k largest elements while iterating through the array, we utilize a min-heap (implemented via std::priority_queue in C++). A min-heap allows us to maintain the top k elements seen so far. If a new element is larger than the smallest element in our heap (the root), we replace the root with this new element.

class Solution {
    std::vector<int> minHeapToVector(std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap) {
        std::vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top());
            minHeap.pop();
        }
        std::reverse(result.begin(), result.end());
        return result;
    }
    
  public:
    std::vector<int> kLargest(std::vector<int>& arr, int k) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
        
        for( int i : arr ) {
            if( minHeap.size() < k )
                minHeap.push(i);
            else if( minHeap.top() <= i ) {
                minHeap.pop();
                minHeap.push(i);
            }
        }
        
        return minHeapToVector(minHeap);
    }
};

Complexity Analysis

Using a min-heap guarantees optimal performance for large datasets. Inserting an element into a heap of size k takes O(log k) time. Since we iterate over all N elements in the array, the overall time complexity is O(N log k). The space complexity is O(k) because the priority queue stores at most k elements at any given time. This is highly efficient and satisfies the problem constraints seamlessly.