### K Largest Elements From List (Main Thread)

Here is the interview question prompt, presented for reference.

We're given a list or array of numbers, like the following:

`const nums = [5, 16, 7, 9, -1, 4, 3, 11, 2]`

Can you write an algorithm to find the `k` largest values in a list of `n` elements? If `k` were `3`, we'd want the three largest numbers returned. The correct logic would return `[16, 11, 9]`. Order is not a consideration.

Can you find more than one approach to this problem?

### Constraints

• Length of the array <= `100000`
• The array will contain values between `-1000000000` and `1000000000`
• The final answer will always fit in the integer range
• Expected time complexity : `O(n logk)` where `k` is the size of the heap
• Expected space complexity : `O(k)`

You can see the full challenge with visuals at this link.

Challenges • Asked almost 6 years ago by Jake from AlgoDaily Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for K Largest Elements From List. Dmitry Pavlov Commented on Sep 04, 2021:

Hi!

I think there is a mistake in lecture about type of `PQ` and its relation with space complexity

If expected space complexity is `O(k)` then we need use `min-PQ` so when capacity reached `k` we be able to pop out min value so far and add new value that is greater then popped

Here is my solution in Java

SNIPPET
``````import java.util.*;

public class Main {

public static int[] kLargest(int[] nums, int k) {
int n = nums.length;

PriorityQueue pq = new PriorityQueue(k, (a, b) -> a - b);
for (int i = 0; i < n; i++) {
int val = nums[i];
if (pq.size() < k) {
} else {
int min = pq.peek();
if (val > min) {
pq.poll();
}
}
}

int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.poll();
}
return result;
}

public static void main(String[] args) {
// print [-1, 2, 9, 11, 17, 29]
System.out.println(
Arrays.toString(Main.kLargest(new int[] {29, 17, 9, -1, -3, 11, 2}, 6))
);
// print [9, 11, 16]
System.out.println(
Arrays.toString(Main.kLargest(new int[] {5, 16, 7, 9, -1, 4, 3, 11, 2}, 3))
);
}

}

````````` Dmitry Pavlov Commented on Sep 06, 2021:

Hi, there!

On Safari version 14.1 images from lecture are displayed 90 degree rotated clockwise. MacOS Big Sur, Version 11.3.1