Print K largest(or smallest) elements in an array

// Java code for k largest elements in an array
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class GFG {
    public static void kLargest(Integer[] arr, int k)
    {
        // Sort the given array arr in reverse order
        // This method doesn't work with primitive data
        // types. So, instead of int, Integer type
        // array will be used
        Arrays.sort(arr, Collections.reverseOrder());

        // Print the first kth largest elements
        for (int i = 0; i < k; i++)
            System.out.print(arr[i] + " ");
    }

    // This code is contributed by Niraj Dubey
    public static ArrayList<Integer> kLargest(int[] arr,
                                              int k)
    {
        // Convert using stream
        Integer[] obj_array
            = Arrays.stream(arr).boxed().toArray(
                Integer[] ::new);
        Arrays.sort(obj_array, Collections.reverseOrder());
        ArrayList<Integer> list = new ArrayList<>(k);

        for (int i = 0; i < k; i++)
            list.add(obj_array[i]);

        return list;
    }

      // Driver code
    public static void main(String[] args)
    {
        Integer arr[]
            = new Integer[] { 1, 23, 12, 9, 30, 2, 50 };
        int k = 3;
        kLargest(arr, k);

        // This code is contributed by Niraj Dubey
        // What if primitive datatype array is passed and
        // wanted to return in ArrayList<Integer>
        int[] prim_array = { 1, 23, 12, 9, 30, 2, 50 };
        kLargest(prim_array, k);
    }
}
// This code is contributed by Kamal Rawal

import java.io.*;
import java.util.*;

public class GFG {

    public static int findKthLargest(int[] arr, int n,
                                         int k)
    {
        int low = Integer.MAX_VALUE,
                high = Integer.MIN_VALUE;

        // Find the minimum and maximum elements in the
        // array
        for (int i : arr) {
            low = Math.min(low, i);
            high = Math.max(high, i);
        }

        // Perform binary search on the range of elements
        // between low and high
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int count = 0;

            // Count the number of elements greater than mid
            // in the array
            for (int i : arr) {
                if (i > mid) {
                    count++;
                }
            }

            // If there are at least K elements greater than
            // mid, search the right half
            if (count >= k) {
                low = mid + 1;
            }
            // Otherwise, search the left half
            else {
                high = mid - 1;
            }
        }

        // Return the Kth largest element
        return high;
    }

    public static void printKLargest(int[] arr, int n,
                                     int k)
    {
        // Find the Kth largest element
        int kthLargest = findKthLargest(arr, n, k);

        // Print the K largest elements in decreasing order
        for (int i : arr) {
            if (i >= kthLargest) {
                System.out.print(" " + i);
            }
        }
    }

    public static void main(String[] args)
    {
        int[] arr = { 12, 5, 787, 1, 23 };
        int n = arr.length;
        int k = 2;

        System.out.print("K largest elements:");
        printKLargest(arr, n, k);
    }
}
// This code is contributed by Rohit Singh

public class KthLargestElements {
    
    // Function to swap two integers
    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    // Partition the array around the last element and get the position of the pivot element in the sorted array
    static int partition(int[] arr, int l, int r) {
        int x = arr[r];
        int i = l;
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] <= x) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, r);
        return i;
    }

    // This function stops at the K'th largest element in arr[l..r] using QuickSort-based method
    static void kthLargest(int[] arr, int l, int r, int k, int N) {
        // Partition the array around the last element and get the position of the pivot element in the sorted array
        int pos = partition(arr, l, r);

        // If the position is the same as k
        if (pos - l == k - 1)
            return;

        // If the position is less, recurse for the right subarray
        else if (pos - l < k - 1)
            kthLargest(arr, pos + 1, r, k - pos + l - 1, N);

        // Else, recurse for the left subarray
        else
            kthLargest(arr, l, pos - 1, k, N);
    }

    public static void main(String[] args) {
        int[] arr = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
        int N = arr.length;
        int k = 3;

        // For Largest
        kthLargest(arr, 0, N - 1, k, N);

        // Print K Largest numbers
        System.out.print(k + " largest elements are: ");
        for (int i = N - 1; i >= N - k; i--)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
}

// Java code for k largest elements in an array
import java.util.*;

class GFG {

    // Function to find k largest array element
    static void kLargest(int a[], int n, int k)
    {
        // Implementation using
        // a Priority Queue
        PriorityQueue<Integer> pq
            = new PriorityQueue<Integer>();

        for (int i = 0; i < n; ++i) {

            // Insert elements into
            // the priority queue
            pq.add(a[i]);

            // If size of the priority
            // queue exceeds k
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // Print the k largest element
        while (!pq.isEmpty()) {
            System.out.print(pq.peek() + " ");
            pq.poll();
        }
        System.out.println();
    }
    // Driver Code
    public static void main(String[] args)
    {
        int a[]
            = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
        int n = a.length;
        int k = 3;
        System.out.print(k + " largest elements are : ");
        // Function Call
        kLargest(a, n, k);
    }
};