Solving k largest(or smallest) elements in an array.

Question: Write an efficient program for printing k largest elements in an array. Elements in an array can be in any order.
For example: if the given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30, and 23.

There are a few different ways to do this. One way would be to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them. Another way would be to first sort the array, then print the last k elements.

This is a common Amazon Interview Question.

What is the most efficient way?

The most efficient way would be to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them.

Here is one possible implementation in JavaScript:

function printKLargest(arr, k) {
  // create an empty list to track the k largest elements
  var kLargest = [];

  // iterate through the array
  for (var i = 0; i < arr.length; i++) {
    // if the list is not full, simply add the element to the list
    if (kLargest.length < k) {
      kLargest.push(arr[i]);
    }
    // if the list is full, compare the current element to the smallest element in the list
    // if the current element is larger, replace the smallest element with the current element
    else {
      var min = Math.min.apply(null, kLargest);
      if (arr[i] > min) {
        var index = kLargest.indexOf(min);
        kLargest[index] = arr[i];
      }
    }
  }

  // print the k largest elements
  return kLargest;
}
//Driver Code
const args = [30,4,8,8,8];

const ans = printKLargest(args,2)
// Will print [30,8] 2 largest numbers in array
console.log(ans)

Here is the code in Java.

public class printKLargest {
  public static void printKLargest(ArrayList<Integer> arr, int k) {
    // create an empty list to track the k largest elements
    ArrayList<Integer> kLargest = new ArrayList<Integer>();
    // iterate through the array
    for (int i = 0; i < arr.size(); i++) {
      // if the list is not full, simply add the element to the list
      if (kLargest.size() < k) {
        kLargest.add(arr.get(i));
      }
      // if the list is full, compare the current element to the smallest element in the list
      // if the current element is larger, replace the smallest element with the current element
      else {
        int min = Collections.min(kLargest);
        if (arr.get(i) > min) {
          int index = kLargest.indexOf(min);
          kLargest.set(index, arr.get(i));
        }
      }
    }
    // print the k largest elements
    return kLargest;
  }
}

The most efficient way to print the k largest elements in an array is to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them.