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 7 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) {
                pq.add(val);
            } else {
                int min = pq.peek();
                if (val > min) {
                    pq.poll();
                    pq.add(val);
                }
            }
        }

        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