How to Solve K Largest Elements
K Largest Elements Introduction
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
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
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.
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 + " ");
}
}
}1import java.util.PriorityQueue;
2
3public class KthLargestElement {
4 public static int[] findKLargest(int[] nums, int k) {
5 PriorityQueue<Integer> minHeap = new PriorityQueue<>();
6 for (int num : nums) {
7 minHeap.offer(num);
8 if (minHeap.size() > k) {
9 minHeap.poll();
10 }
11 }
12
13 int[] kLargest = new int[k];
14 for (int i = k - 1; i >= 0; i--) {
15 kLargest[i] = minHeap.poll();
16 }
17 return kLargest;
18 }
19
20 public static void main(String[] args) {
21 int[] nums = {3, 7, 2, 1, 8, 5, 9};
22 int k = 3;
23 int[] result = findKLargest(nums, k);
24 System.out.print("The " + k + " largest elements in the array are: ");
25 for (int num : result) {
26 System.out.print(num + " ");
27 }
28 }
29}Time/Space Complexity Analysis
- Time Complexity: O(n log k), where n is the length of the array.
- Space Complexity: O(k), we use a heap/priority queue to store the k largest elements, so the space required is proportional to the value of k. In the worst case, if k is equal to the length of the array (k = n), the space complexity would be O(n).
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
