Sunday, December 3, 2023
HomeDSASolving k largest(or smallest) elements in an array.

# 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) {
}
// 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.

RELATED ARTICLES