Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

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 8 years ago by Team AlgoDaily

Team 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  min) {
                    pq.poll();
                    pq.add(val);
                }
            }
        }

        int[] result = new int[k];
        for (int i = 0; i
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