K Largest Elements

How to Solve K Largest Elements

K Largest Elements Introduction

The K Largest Elements problem asks us to print k largest elements in an array, from largest to smallest. We can easily solve this problem by iterating through the array and adding elements to our heap and maintaining the size to be at most K.

K Largest Elements Problem

Write an efficient program for printing k largest elements in an array. Largest elements are returned in order largest to smallest.

Example Inputs and Outputs

Example 1

Input: nums = [3, 7, 2, 1, 8, 5, 9], k = 3
Output: [9, 8, 7]

K Largest Elements Solutions

Heap:

To find the k largest elements in the array, we utilize a heap/ priority queue data structure. Both the Python and Java solutions follow a similar approach. We iterate through each number in the array and add it to the heap. However, we maintain the size of the heap to be at most k, ensuring that it contains the k largest elements encountered so far.

In the Python solution, we use the heapq module to create a min heap. For each number, we push it onto the heap using heapq.heappush. If the size of the heap exceeds k, we remove the smallest element from the heap using heapq.heappop. After iterating through all the numbers, the top k elements in the heap will be the k largest elements in the array. We retrieve them from the heap using heapq.heappop and return them as the result.

Priority Queue:

Similarly, in the Java solution, we use the PriorityQueue class, which by default implements a min heap. We create a PriorityQueue object called minHeap to store the numbers. For each number in the array, we add it to the minHeap using the offer method. If the size of the minHeap exceeds k, we remove the smallest element from the minHeap using the poll method. Finally, the top k elements in the minHeap will be the k largest elements in the array. We retrieve them from the minHeap by repeatedly calling the poll method and store them in an array called kLargest. Since the PriorityQueue stores elements in ascending order, we populate kLargest in reverse order (from the end to the beginning) to obtain the k largest elements in descending order.

We utilize a heap data structure in JavaScript. We maintain a heap array that contains the k largest elements encountered so far. For each number in the input array, we add it to the heap array. If the heap size exceeds k, we sort the heap in descending order and keep only the top k elements. By the end of the iteration, the heap array contains the k largest elements in descending order. We can then return this array as the result.

Implementation Examples

Java Example

import java.util.PriorityQueue;

public class KthLargestElement {
    public static int[] findKLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

int[] kLargest = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            kLargest[i] = minHeap.poll();
        }
        return kLargest;
    }

public static void main(String[] args) {
        int[] nums = {3, 7, 2, 1, 8, 5, 9};
        int k = 3;
        int[] result = findKLargest(nums, k);
        System.out.print("The " + k + " largest elements in the array are: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Time/Space Complexity Analysis