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.

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.