Sample Problem: K largest elements in Java

Problem:

Write a program that efficiently prints the K largest elements in an array, regardless of the order in which the elements appear.

Example:

Input: arr[] = [1, 23, 12, 9, 30, 2, 50], K = 3

Output: 50, 30 and 23.

Solutions:

Sorting:

Sort the array in descending order in O(N*logN) time.

Print the first K elements of the sorted array in O(K) time.

Overall time complexity: O(N*logN + K).

Max Heap:

Build a Max Heap in O(N) time.

Extract the maximum element K times in O(K*logN) time.

Overall time complexity: O(N + K*logN).

Min Heap:

Create a Min Heap of the first K elements in O(K) time.

For each element from the (K+1)th index, compare it with the top element of the Min Heap.

If the current element is greater than the top element, remove the top element and insert the current element in the Min Heap.

Finally, print the elements of the Min Heap.

Overall time complexity: O((N-K)*logK).

Implementation:

import java.util.*;

public class KLargestElements {

public static void printKLargest(int[] arr, int k) {

PriorityQueue<Integer> pq = new PriorityQueue<>();

scss

Copy code

    // Add first K elements to the Min Heap

    for(int i=0; i<k; i++)

        pq.add(arr[i]);

        

    // Compare remaining elements with the Min Heap's top element

    for(int i=k; i<arr.length; i++) {

        if(arr[i] > pq.peek()) {

            pq.poll();

            pq.add(arr[i]);

        }

    }

    

    // Print the K largest elements

    while(!pq.isEmpty())

        System.out.print(pq.poll() + " ");

}

public static void main(String[] args) {

    int[] arr = {1, 23, 12, 9, 30, 2, 50};

    int k = 3;

    

    printKLargest(arr, k);

}

}

Output: 50 30 23

Time Complexity: O((N-K)*logK)

Auxiliary Space: O(K)

Conclusion:

In this problem, we have explored three different approaches to find the K largest elements in an array. The Min Heap approach is the most efficient, with a time complexity of O((N-K)*logK), which is better than the time complexities of the other two approaches.