Open In App

Print K largest(or smallest) elements in an array

Last Updated : 29 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given an array arr[] of size N, the task is to printing K largest elements in an array.
Note: Elements in output array can be in any order

Examples:

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

Input:  [11, 5, 12, 9, 44, 17, 2], K = 2
Output: 44, 17

Recommended Practice

K largest elements in an array using Sorting:

Sort the input array in descending order so that the first K elements in the array are the K largest elements

Follow the below steps to solve the problem:

  • Sort the elements in descending order
  • Print the first K numbers of the sorted array

Below is the implementation of the above approach:

C++
// C++ code for K largest elements in an array
#include <bits/stdc++.h>
using namespace std;

void kLargest(int arr[], int n, int k)
{
    // Sort the given array arr in reverse order.
    sort(arr, arr + n, greater<int>());

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

// Driver code
int main()
{
    int arr[] = { 1, 23, 12, 9, 30, 2, 50 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    kLargest(arr, n, k);
}

// This code is contributed by Aditya Kumar (adityakumar129)
C
// C code for k largest elements in an array
#include <stdio.h>
#include <stdlib.h>

// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
    return (*(int*)b - *(int*)a);
}

void kLargest(int arr[], int n, int k)
{
    // Sort the given array arr in reverse order.
    qsort(arr, n, sizeof(int), cmpfunc);
    // Print the first kth largest elements
    for (int i = 0; i < k; i++)
        printf("%d ", arr[i]);
}

// Driver code
int main()
{
    int arr[] = { 1, 23, 12, 9, 30, 2, 50 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    kLargest(arr, n, k);
}

// This code is contributed by Aditya Kumar (adityakumar129)
Java
// 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
Python
''' Python3 code for k largest elements in an array'''


def kLargest(arr, k):
    # Sort the given array arr in reverse
    # order.
    arr.sort(reverse=True)
    # Print the first kth largest elements
    for i in range(k):
        print(arr[i], end=" ")


# Driver code
arr = [1, 23, 12, 9, 30, 2, 50]
# n = len(arr)
k = 3
kLargest(arr, k)

# This code is contributed by shreyanshi_arun.
C#
// C# code for k largest elements in an array
using System;

class GFG {
    public static void kLargest(int[] 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
        Array.Sort(arr);
        Array.Reverse(arr);

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

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

// This code contributed by Rajput-Ji
Javascript
<script>

// JavaScript code for k largest
// elements in an array

function kLargest(arr, n, k)
{
    // Sort the given array arr in reverse
    // order.
    arr.sort((a, b) => b - a);

    // Print the first kth largest elements
    for (let i = 0; i < k; i++)
        document.write(arr[i] + " ");
}

// driver program
    let arr = [ 1, 23, 12, 9, 30, 2, 50 ];
    let n = arr.length;
    let k = 3;
    kLargest(arr, n, k);


// This code is contributed by Manoj.

</script>
PHP
<?php 
// PHP code for k largest 
// elements in an array

function kLargest(&$arr, $n, $k)
{
    // Sort the given array arr 
    // in reverse order.
    rsort($arr);

    // Print the first kth 
    // largest elements
    for ($i = 0; $i < $k; $i++)
        echo $arr[$i] . " ";
}

// Driver Code
$arr = array(1, 23, 12, 9, 
                30, 2, 50);
$n = sizeof($arr);
$k = 3;
kLargest($arr, $n, $k);

// This code is contributed 
// by ChitraNayal
?>

Output
50 30 23 

Time complexity: O(N * log(N))
Auxiliary Space: O(1)

K largest elements in an array using Binary Search:

The idea is to find the Kth largest element of the array and then print all the elements which are greater than or equal to Kth largest Element. The Kth largest element can be found using binary search by defining a search range based on the minimum and maximum values in the input array. In each iteration of binary search, count the larger than the midpoint and update the search range accordingly. This process continues until the range collapses to a single element, which is the kth largest element.

Follow the given steps to solve the problem:

  • Initialize low and high to minimum and maximum element of the array denoting the range within which the answer lies.
  • Apply Binary Search on this range. 
    • If the selected element by calculating mid has less than K elements lesser to it then increase the number that is low = mid + 1.
    • Otherwise, Decrement the high pointer, i.e high = mid.
    • The Binary Search will terminate when only one element remains in the answer space that would be the Kth largest element.
  • Print all the elements which are greater than or equal to Kth largest element.

Below is the implementation of above approach:

C++
// C++ code to implement the binary search approach
#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

// Function to find the Kth largest element in the array
// using binary search
int findKthLargest(int arr[], int n, int k)
{
    int low = INT_MAX, high = INT_MIN;

    // Find the minimum and maximum elements in the array
    for (int i = 0; i < n; i++) {
        low = min(low, arr[i]);
        high = max(high, arr[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 = 0; i < n; i++) {
            if (arr[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;
}

// Function to print the K largest elements in the array
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 = 0; i < n; i++) {
        if (arr[i] >= kthLargest) {
            cout << arr[i] << " ";
        }
    }
    cout << endl;
}

// Driver code
int main()
{
    int arr[] = { 12, 5, 787, 1, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    cout << "K largest elements: ";
    printKLargest(arr, n, k);

    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot
Java
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
Python3
# Python code to implement the binary search approach
# Function to find the Kth largest element in the array using binary search
def findKthLargest(arr, n, k):
    low = float('inf')
    high = float('-inf')

    # Find the minimum and maximum elements in the array
    for i in range(n):
        low = min(low, arr[i])
        high = max(high, arr[i])

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

        # Count the number of elements greater than mid in the array
        for i in range(n):
            if arr[i] > mid:
                count += 1

        # 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


# Function to print the K largest elements in the array
def printKLargest(arr, n, k):
    # Find the Kth largest element
    kthLargest = findKthLargest(arr, n, k)

    # Print the K largest elements in decreasing order
    print("K largest elements:", end=" ")
    for i in range(n):
        if arr[i] >= kthLargest:
            print(arr[i], end=" ")
    print()


# Driver code
if __name__ == '__main__':
    arr = [12, 5, 787, 1, 23]
    n = len(arr)
    k = 2
    printKLargest(arr, n, k)

# This code is contributed by Susobhan Akhuli
C#
using System;

namespace KthLargestElement
{
    class Program
    {
        static int FindKthLargest(int[] arr, int n, int k)
        {
            int low = int.MaxValue;
            int high = int.MinValue;

            // Find the minimum and maximum elements in the array
            foreach (int num in arr)
            {
                low = Math.Min(low, num);
                high = Math.Max(high, num);
            }

            // 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
                foreach (int num in arr)
                {
                    if (num > 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;
        }

        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
            foreach (int num in arr)
            {
                if (num >= kthLargest)
                {
                    Console.Write(num + " ");
                }
            }
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            int[] arr = { 12, 5, 787, 1, 23 };
            int n = arr.Length;
            int k = 2;

            Console.Write("K largest elements: ");
            PrintKLargest(arr, n, k);
        }
    }
}
Javascript
// Function to find the Kth largest element in the array using binary search
function findKthLargest(arr, k) {
    let low = Number.POSITIVE_INFINITY;
    let high = Number.NEGATIVE_INFINITY;

    // Find the minimum and maximum elements in the array
    for (let i = 0; i < arr.length; i++) {
        low = Math.min(low, arr[i]);
        high = Math.max(high, arr[i]);
    }

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

        // Count the number of elements greater than mid in the array
        for (let i = 0; i < arr.length; i++) {
            if (arr[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;
}

// Function to print the K largest elements in the array
function printKLargest(arr, k) {
    // Find the Kth largest element
    const kthLargest = findKthLargest(arr, k);

    // Print the K largest elements in decreasing order
    process.stdout.write("K largest elements: ");
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] >= kthLargest) {
            process.stdout.write(arr[i] + " ");
        }
    }
    console.log();
}

// Driver code
const arr = [12, 5, 787, 1, 23];
const k = 2;
printKLargest(arr, k);

Output
K largest elements: 787 23 

Time complexity: O(n * log (mx-mn)), where mn be minimum and mx be maximum element of array.
Auxiliary Space: O(1)

K largest elements in an array using Quick Sort partitioning algorithm:

This is an optimization over method 1, if QuickSort is used as a sorting algorithm in first step. In QuickSort, pick a pivot element, then move the pivot element to its correct position and partition the surrounding array. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th largest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. 

Follow the given steps to solve the problem:

  • Run quick sort algorithm on the input array
  • In this algorithm pick a pivot element and move it to it’s correct position
  • Now, if index of pivot is equal to K then return , else if the index of pivot is less than K, then recur for the right subarray, else recur for the left subarray. 
  • Repeat this process until the element at index K is not found.

Below is the implementation of the above approach:

C++
// c++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int l, int r);

// This function stops at K'th largest element in arr[l..r]
// using QuickSort based method.
void KthLargest(int arr[], int l, int r, int K, int N)
{

    // Partition the array around last element and get
    // position of pivot element in sorted array
    int pos = partition(arr, l, r);

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

    // If position is less, recur
    // for right subarray
    else if (pos - l < K - 1)
        return KthLargest(arr, pos + 1, r, K - pos + l - 1,
                          N);

    // Else recur for left subarray
    else
        return KthLargest(arr, l, pos - 1, K, N);
}

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }

    swap(&arr[i], &arr[r]);
    return i;
}

// Driver code
int main()
{
    int arr[]
        = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };

    int N = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

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

    // Print KLargest no.

    cout << k << " largest elements are : ";
    for (int i = N - 1; i >= N - k; i--)
        cout << arr[i] << "  ";

    return 0;
}
C
#include <stdio.h>

// Function to swap two integers
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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

// This function stops at the K'th largest element in arr[l..r] using QuickSort-based method
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 position is the same as K
    if (pos - l == K - 1)
        return;

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

    // Else, recurse for the left subarray
    else
        return KthLargest(arr, l, pos - 1, K, N);
}

int main() {
    int arr[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

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

    // Print K Largest numbers
    printf("%d largest elements are: ", k);
    for (int i = N - 1; i >= N - k; i--)
        printf("%d ", arr[i]);
    
    printf("\n");

    return 0;
}
Java
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();
    }
}
Python3
def partition(arr, l, r):
    x = arr[r]  # Choose the last element as the pivot
    i = l

    # Iterate through the array and move elements smaller than the pivot to the left
    for j in range(l, r):
        if arr[j] <= x:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1

    # Swap the pivot element with the element at index 'i'
    arr[i], arr[r] = arr[r], arr[i]
    return i

def kthLargest(arr, l, r, k, N):
    # Partition the array around the pivot
    pos = partition(arr, l, r)

    # If the position is the same as 'k', we have found the kth largest element
    if pos - l == k - 1:
        return

    # If the position is less than 'k', recurse for the right subarray
    elif pos - l < k - 1:
        kthLargest(arr, pos + 1, r, k - pos + l - 1, N)

    # Otherwise, recurse for the left subarray
    else:
        kthLargest(arr, l, pos - 1, k, N)

if __name__ == "__main__":
    arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45]
    N = len(arr)
    k = 3

    # Find the kth largest elements
    kthLargest(arr, 0, N - 1, k, N)

    # Print K Largest numbers
    print(f"{k} largest elements are:", end=" ")
    for i in range(N - 1, N - k - 1, -1):
        print(arr[i], end=" ")

    print()
C#
using System;

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 than k, recurse for the right subarray
        else if (pos - l < k - 1)
            KthLargest(arr, pos + 1, r, k - pos + l - 1, N);

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

    public static void Main()
    {
        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
        Console.Write($"{k} largest elements are: ");
        for (int i = N - 1; i >= N - k; i--)
            Console.Write($"{arr[i]} ");

        Console.WriteLine();
    }
}
Javascript
using System;

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 than k, recurse for the right subarray
        else if (pos - l < k - 1)
            KthLargest(arr, pos + 1, r, k - pos + l - 1, N);

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

    public static void Main()
    {
        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
        Console.Write($"{k} largest elements are: ");
        for (int i = N - 1; i >= N - k; i--)
            Console.Write($"{arr[i]} ");

        Console.WriteLine();
    }
}

Output
3 largest elements are : 88  50  96  

Time Complexity: O(N2) in worst case(O(N) on average).
Auxiliary Space: O(N)

Note: We can improve on the standard quicksort algorithm by using the random() function. Instead of using the pivot element as the last element, we can randomly choose the pivot element randomly.

K largest elements in an array using Priority Queue(Min-Heap):

The intuition behind this approach is to maintain a minheap (priority queue) of size K while iterating through the array. Doing this ensures that the min heap always contains the K largest elements encountered so far. If the size of the min heap exceeds K, remove the smallest element this step ensures that the heap maintains the K largest elements encountered so far. In the end, the min heap contains the K largest elements of the array.

Follow the below steps to solve the problem:

  • Initialize a min heap (priority queue) pq.
  • For each element in the array:
    • Push the element onto the min heap.
    • If the size of the min heap exceeds K, pop (remove) the smallest element from the min heap. This step ensures that the min heap maintains the K largest elements encountered so far.
  • After processing all elements, the min heap will contain the K largest elements of the array.

Below is the implementation of the above approach:

C++
// C++ code for k largest elements in an array
#include <bits/stdc++.h>
using namespace std;

// Function to find k largest array element
void kLargest(vector<int>& v, int N, int K)
{
    // Implementation using
    // a Priority Queue
    priority_queue<int, vector<int>, greater<int> > pq;

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

        // Insert elements into
        // the priority queue
        pq.push(v[i]);

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

    // Print the k largest element
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
}

// driver program
int main()
{
    // Given array
    vector<int> arr
        = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };
    // Size of array
    int n = arr.size();
    int k = 3;
    cout << k << " largest elements are : ";
    kLargest(arr, n, k);
}
Java
// 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);
    }
};
Python3
# Python code for k largest elements in an array
import heapq

# Function to find k largest array element


def kLargest(v, N, K):

    # Implementation using
    # a Priority Queue
    pq = []
    heapq.heapify(pq)

    for i in range(N):

        # Insert elements into
        # the priority queue
        heapq.heappush(pq, v[i])

        # If size of the priority
        # queue exceeds k
        if (len(pq) > K):
            heapq.heappop(pq)

    # Print the k largest element
    while(len(pq) != 0):
        print(heapq.heappop(pq), end=' ')
    print()





# driver program

# Given array
arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45]
# Size of array
n = len(arr)
k = 3
print(k, " largest elements are : ", end='')
kLargest(arr, n, k)
C#
using System;
using System.Linq;
using System.Collections.Generic;

class GFG 
{

  // Function to find k largest array element
  static void kLargest(int[] a, int n, int k)
  {

    // Implementation using a SortedSet
    SortedSet<int> pq = new SortedSet<int>();

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

      // Insert elements into the SortedSet
      pq.Add(a[i]);

      // If size of the SortedSet exceeds k
      if (pq.Count > k) {
        pq.Remove(pq.Min);
      }
    }

    // Print the k largest element
    while (pq.Count > 0) {
      Console.Write(pq.Max + " ");
      pq.Remove(pq.Max);
    }
    Console.WriteLine();
  }


  // 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;
    Console.Write(k + " largest elements are : ");

    // Function call
    kLargest(a, n, k);
   
  }
}
Javascript
// Function to find k largest array element
function kLargest(v, N, K) {
  // Implementation using
  // a Priority Queue
  const pq = [];
  v.forEach(val => pq.push(val));
  pq.sort((a, b) => a - b);

  // If size of the priority
  // queue exceeds k
  if (pq.length > K) {
    pq.splice(0, pq.length - K);
  }

  // Print the k largest element
  while (pq.length !== 0) {
    console.log(pq.shift());
  }
  console.log();
}

 

// driver program

// Given array
const arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45];
// Size of array
const n = arr.length;
const k = 3;
console.log(`${k} largest elements are: `);
kLargest(arr, n, k);


// This code is contributed by adityamaharshi21

Output
3 largest elements are : 50 88 96 

Time Complexity: O(N * log(K))
Auxiliary Space: O(K)



Previous Article
Next Article

Similar Reads

Rearrange an array in order - smallest, largest, 2nd smallest, 2nd largest, ..
Given an array of integers, the task is to print the array in the order - smallest number, the Largest number, 2nd smallest number, 2nd largest number, 3rd smallest number, 3rd largest number, and so on..... Examples: Input : arr[] = [5, 8, 1, 4, 2, 9, 3, 7, 6] Output :arr[] = {1, 9, 2, 8, 3, 7, 4, 6, 5} Input : arr[] = [1, 2, 3, 4] Output :arr[] =
7 min read
Average of remaining elements after removing K largest and K smallest elements from array
Given an array of N integers. The task is to find the average of the numbers after removing k largest elements and k smallest element from the array i.e. calculate the average value of the remaining N - 2K elements. Examples: Input: arr = [1, 2, 4, 4, 5, 6], K = 2Output: 4Remove 2 smallest elements i.e. 1 and 2Remove 2 largest elements i.e. 5 and 6
5 min read
Minimize swaps required to make the first and last elements the largest and smallest elements in the array respectively
Given an array arr[] consisting of N integers, the task is to find the minimum number of adjacent swaps required to make the first and the last elements in the array the largest and smallest element present in the array respectively. Examples: Input: arr[] = {1, 3, 2}Output: 2Explanation:Initially the array is {1, 3, 2}.Operation 1: Swap element at
8 min read
Mean of given array after removal of K percent of smallest and largest array elements
Given an array arr[] and an integer K, the task is to remove K % percent array elements from the smallest and largest array elements and calculate the mean of the remaining array. Examples: Input: arr[] = {6, 2, 7, 5, 1, 2, 0, 3, 10, 2, 5, 0, 5, 5, 0, 8, 7, 6, 8, 0}, K = 5Output: 4.00000Explanation:There are 20 elements in the array. Therefore, 5%
6 min read
Minimize swaps required to place largest and smallest array elements at first and last array indices
Given an array arr[] of size N, the task is to find the minimum count of adjacent swaps required to rearrange the array elements such that the largest and the smallest array element present on the first and the last indices of the array respectively. Examples: Input: arr[] = {33, 44, 11, 12} Output: 2 Explanation: Swapping the pair (arr[0], arr[1])
8 min read
Make all array elements equal by repeatedly replacing largest array element with the second smallest element
Given an array arr[] of size N, the task is to count the number of operations required to make all array elements equal by replacing the largest array element with the second-largest array element, which is strictly smaller than the largest array element. Examples: Input: arr[ ] = {1, 1, 2, 2, 3}Output: 4Explanation: A total of 4 operations are req
6 min read
Print X array elements closest to the Kth smallest element in the array
Given two integers K, X, and an array arr[] consisting of N distinct elements, the task is to find X elements closest to the Kth smallest element from the given array. Examples: Input: arr[] = {1, 2, 3, 4, 10}, K = 3, X = 2Output: 2 3Explanation: Kth smallest element present in the given array is 3 and X(= 2) closest array elements to 3 are {2, 3}
15+ min read
Find the smallest and second smallest elements in an array
Given an array arr[] of size N, find the smallest and second smallest element in an array. Examples: Input: arr[] = {12, 13, 1, 10, 34, 1} Output: 1 10Explanation: The smallest element is 1 and second smallest element is 10. Input: arr[] = {111, 13, 25, 9, 34, 1}Output: 1 9Explanation: The smallest element is 1 and second smallest element is 9. Rec
14 min read
Maximize distance between smallest and largest Array elements by a single swap
Given an arr[] consisting of N elements in the range [1, N], the task is to maximize the distance between smallest and largest array element by a single swap. Examples: Input: arr[] = {1, 4, 3, 2} Output: 3 Explanation: Swapping of arr[1] and arr[3] maximizes the distance. Input: arr[] = {1, 6, 5, 3, 4, 7, 2} Output: 6 Explanation: Swapping of arr[
5 min read
Minimize absolute difference between the smallest and largest array elements by minimum increment decrement operations
Given an array arr[] consisting of N positive integers, the task is to minimize the number of operations required to minimize the absolute difference between the smallest and largest elements present in the array. In each operation, subtract 1 from an array element and increment 1 to another array element. Examples: Input: arr[] = {1, 6}Output: 2Ex
8 min read