# k largest(or smallest) elements in an array

• Difficulty Level : Medium
• Last Updated : 24 Aug, 2022

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.

Recommended Practice

Method 1 (Use Bubble k times)
Thanks to Shailendra for suggesting this approach.
1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(n*k)

Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 2 (Use temporary array)
K largest elements from arr[0..n-1]

1) Store the first k elements in a temporary array temp[0..k-1].
2) Find the smallest element in temp[], let the smallest element be min
3-a) For each element x in arr[k] to arr[n-1]. O(n-k)
If x is greater than the min then remove min from temp[] and insert x
3-b)Then, determine the new min from temp[]. O(k)
4) Print final k elements of temp[]

Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + k*log(k))
Thanks to nesamani1822 for suggesting this method.

Method 3(Use Sorting)
1) Sort the elements in descending order in O(n*log(n))
2) Print the first k numbers of the sorted array O(k).

Following is the implementation of the above.

## C++

 `// C++ code for k largest elements in an array``#include ``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 program``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 ``#include ` `// 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 program``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.Arrays;``import` `java.util.Collections;``import` `java.util.ArrayList;` `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 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 list = ``new` `ArrayList<>(k);` `        ``for` `(``int` `i = ``0``; i < k; i++)``            ``list.add(obj_array[i]);``    ` `        ``return` `list;``    ``}` `    ``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``        ``int``[] prim_array = { ``1``, ``23``, ``12``, ``9``, ``30``, ``2``, ``50` `};``          ``System.out.print(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 program``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`

## PHP

 ``

## Javascript

 ``

Output

`50 30 23 `

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

Method 4 (Use Max Heap)
1) Build a Max Heap tree in O(n*log(n))
2) Use Extract Max k times to get k maximum elements from the Max Heap O(k*log(n))

Time complexity: O(n*log(n) + k*log(n))

Method 5(Use Order Statistics)
1) Use an order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time O(n)
2) Use QuickSort Partition algorithm to partition around the kth largest number O(n).
3) Sort the k-1 elements (elements greater than the kth largest element) O(k*log(k)). This step is needed only if the sorted output is required.

Time complexity: O(n) if we don’t need the sorted output, otherwise O(n+k*log(k))
Thanks to Shilpi for suggesting the first two approaches.

Method 6 (Use Min Heap)
This method is mainly an optimization of method 2. Instead of using temp[] array, use Min Heap.
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k*log(k))
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is greater than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*log(k))
3) Finally, MH has k largest elements, and the root of the MH is the kth largest element.
Time Complexity: O(k*log(k) + (n-k)*log(k)) without sorted output. If sorted output is needed then O(k*log(k) + (n-k)*log(k) + k*log(k)) so overall it is O(k*log(k) + (n-k)*log(k))

All of the above methods can also be used to find the kth largest (or smallest) element.

## C++

 `#include ``using` `namespace` `std;` `// Swap function to interchange``// the value of variables x and y``int` `swap(``int``& x, ``int``& y)``{``    ``int` `temp = x;``    ``x = y;``    ``y = temp;``}` `// Min Heap Class``// arr holds reference to an integer``// array size indicate the number of``// elements in Min Heap``class` `MinHeap {` `    ``int` `size;``    ``int``* arr;` `public``:``    ``// Constructor to initialize the size and arr``    ``MinHeap(``int` `size, ``int` `input[]);` `    ``// Min Heapify function, that assumes that``    ``// 2*i+1 and 2*i+2 are min heap and fix the``    ``// heap property for i.``    ``void` `heapify(``int` `i);` `    ``// Build the min heap, by calling heapify``    ``// for all non-leaf nodes.``    ``void` `buildHeap();``};` `// Constructor to initialize data``// members and creating mean heap``MinHeap::MinHeap(``int` `size, ``int` `input[])``{``    ``// Initializing arr and size` `    ``this``->size = size;``    ``this``->arr = input;` `    ``// Building the Min Heap``    ``buildHeap();``}` `// Min Heapify function, that assumes``// 2*i+1 and 2*i+2 are min heap and``// fix min heap property for i` `void` `MinHeap::heapify(``int` `i)``{``    ``// If Leaf Node, Simply return``    ``if` `(i >= size / 2)``        ``return``;` `    ``// variable to store the smallest element``    ``// index out of i, 2*i+1 and 2*i+2``    ``int` `smallest;` `    ``// Index of left node``    ``int` `left = 2 * i + 1;` `    ``// Index of right node``    ``int` `right = 2 * i + 2;` `    ``// Select minimum from left node and``    ``// current node i, and store the minimum``    ``// index in smallest variable``    ``smallest = arr[left] < arr[i] ? left : i;` `    ``// If right child exist, compare and``    ``// update the smallest variable``    ``if` `(right < size)``        ``smallest = arr[right] < arr[smallest]``                             ``? right : smallest;` `    ``// If Node i violates the min heap``    ``// property, swap  current node i with``    ``// smallest to fix the min-heap property``    ``// and recursively call heapify for node smallest.``    ``if` `(smallest != i) {``        ``swap(arr[i], arr[smallest]);``        ``heapify(smallest);``    ``}``}` `// Build Min Heap``void` `MinHeap::buildHeap()``{``    ``// Calling Heapify for all non leaf nodes``    ``for` `(``int` `i = size / 2 - 1; i >= 0; i--) {``        ``heapify(i);``    ``}``}` `void` `FirstKelements(``int` `arr[],``int` `size,``int` `k){``    ``// Creating Min Heap for given``    ``// array with only k elements``    ``MinHeap* m = ``new` `MinHeap(k, arr);` `    ``// Loop For each element in array``    ``// after the kth element``    ``for` `(``int` `i = k; i < size; i++) {` `        ``// if current element is smaller``        ``// than minimum element, do nothing``        ``// and continue to next element``        ``if` `(arr[0] > arr[i])``            ``continue``;` `        ``// Otherwise Change minimum element to``        ``// current element, and call heapify to``        ``// restore the heap property``        ``else` `{``            ``arr[0] = arr[i];``            ``m->heapify(0);``        ``}``    ``}``    ``// Now min heap contains k maximum``    ``// elements, Iterate and print``    ``for` `(``int` `i = 0; i < k; i++) {``        ``cout << arr[i] << ``" "``;``    ``}``}``// Driver Program``int` `main()``{` `    ``int` `arr[] = { 11, 3, 2, 1, 15, 5, 4,``                           ``45, 88, 96, 50, 45 };` `    ``int` `size = ``sizeof``(arr) / ``sizeof``(arr[0]);` `    ``// Size of Min Heap``    ``int` `k = 3;` `    ``FirstKelements(arr,size,k);` `    ``return` `0;``}``// This code is contributed by Ankur Goel`

## Java

 `import` `java.io.*;``import` `java.util.*;` `class` `GFG{``  ` `public` `static` `void` `FirstKelements(``int` `arr[],``                                  ``int` `size,``                                  ``int` `k)``{``    ` `    ``// Creating Min Heap for given``    ``// array with only k elements``    ``// Create min heap with priority queue``    ``PriorityQueue minHeap = ``new` `PriorityQueue<>();``    ``for``(``int` `i = ``0``; i < k; i++)``    ``{``        ``minHeap.add(arr[i]);``    ``}``    ` `    ``// Loop For each element in array``    ``// after the kth element``    ``for``(``int` `i = k; i < size; i++)``    ``{``        ` `        ``// If current element is smaller``        ``// than minimum ((top element of``        ``// the minHeap) element, do nothing``        ``// and continue to next element``        ``if` `(minHeap.peek() > arr[i])``            ``continue``;``        ` `        ``// Otherwise Change minimum element``        ``// (top element of the minHeap) to``        ``// current element by polling out``        ``// the top element of the minHeap``        ``else``        ``{``            ``minHeap.poll();``            ``minHeap.add(arr[i]);``        ``}``    ``}``    ` `    ``// Now min heap contains k maximum``    ``// elements, Iterate and print``    ``Iterator iterator = minHeap.iterator();``    ` `    ``while` `(iterator.hasNext())``    ``{``        ``System.out.print(iterator.next() + ``" "``);``    ``}``}` `// Driver code``public` `static` `void` `main (String[] args)``{``    ``int` `arr[] = { ``11``, ``3``, ``2``, ``1``, ``15``, ``5``, ``4``,``                  ``45``, ``88``, ``96``, ``50``, ``45` `};``    ` `    ``int` `size = arr.length;``    ` `    ``// Size of Min Heap``    ``int` `k = ``3``;``    ` `    ``FirstKelements(arr, size, k);``}``}` `// This code is contributed by Vansh Sethi`

## Python3

 `#importing heapq module``#to implement heap``import` `heapq as hq` `def` `FirstKelements(arr, size, k):``    ``# Creating Min Heap for given``    ``# array with only k elements``    ``# Create min heap using heapq module``    ``minHeap ``=` `[]` `    ``for` `i ``in` `range``(k):``        ``minHeap.append(arr[i])``    ``hq.heapify(minHeap)``    ``# Loop For each element in array``    ``# after the kth element` `    ``for` `i ``in` `range``(k, size):``        ``# If current element is smaller``        ``# than minimum ((top element of``        ``# the minHeap) element, do nothing``        ``# and continue to next element` `        ``if` `minHeap[``0``] > arr[i]:``            ``continue``        ``# Otherwise Change minimum element``        ``# (top element of the minHeap) to``        ``# current element by polling out``        ``# the top element of the minHeap``        ``else``:``              ``#deleting top element of the min heap``            ``minHeap[``0``] ``=` `minHeap[``-``1``]``            ``minHeap.pop()``            ``minHeap.append(arr[i])``            ``#maintaining heap again using``            ``# O(n) time operation....``            ``hq.heapify(minHeap)``    ``# Now min heap contains k maximum``    ``# elements, Iterate and print``    ``for` `i ``in` `minHeap:``        ``print``(i, end``=``" "``)`  `# Driver code``arr ``=` `[``11``, ``3``, ``2``, ``1``, ``15``, ``5``, ``4``, ``45``, ``88``, ``96``, ``50``, ``45``]``size ``=` `len``(arr)``# Size of Min Heap``k ``=` `3``FirstKelements(arr, size, k)``'''Code is written by Rajat Kumar.....'''`

## C#

 `using` `System;``using` `System.Collections.Generic;``public` `class` `GFG``{``  ` `public` `static` `void` `FirstKelements(``int` `[]arr,``                                  ``int` `size,``                                  ``int` `k)``{``    ` `    ``// Creating Min Heap for given``    ``// array with only k elements``    ``// Create min heap with priority queue``    ``List<``int``> minHeap = ``new` `List<``int``>();``    ``for``(``int` `i = 0; i < k; i++)``    ``{``        ``minHeap.Add(arr[i]);``    ``}``    ` `    ``// Loop For each element in array``    ``// after the kth element``    ``for``(``int` `i = k; i < size; i++)``    ``{``        ``minHeap.Sort();``      ` `        ``// If current element is smaller``        ``// than minimum ((top element of``        ``// the minHeap) element, do nothing``        ``// and continue to next element``        ``if` `(minHeap[0] > arr[i])``            ``continue``;``        ` `        ``// Otherwise Change minimum element``        ``// (top element of the minHeap) to``        ``// current element by polling out``        ``// the top element of the minHeap``        ``else``        ``{``            ``minHeap.RemoveAt(0);``            ``minHeap.Add(arr[i]);``        ``}``    ``}``    ` `    ``// Now min heap contains k maximum``    ``// elements, Iterate and print  ``    ``foreach` `(``int` `i ``in` `minHeap)``    ``{``        ``Console.Write(i + ``" "``);``    ``}``}` `// Driver code``public` `static` `void` `Main(String[] args)``{``    ``int` `[]arr = { 11, 3, 2, 1, 15, 5, 4,``                  ``45, 88, 96, 50, 45 };``    ``int` `size = arr.Length;``    ` `    ``// Size of Min Heap``    ``int` `k = 3;``    ``FirstKelements(arr, size, k);``}``}` `// This code is contributed by aashish1995.`

## Javascript

 ``

Output

`50 88 96 `

Time Complexity: O(nlogn)
Auxiliary Space: O(n)

Method 7(Using Quick Sort partitioning algorithm):

1. Choose a pivot number.
2. if K is lesser than the pivot_Index then repeat the step.
3. if K == pivot_Index : Print the array (low to pivot to get K-smallest elements and (n-pivot_Index) to n for K-largest elements)
4. if  K > pivot_Index : Repeat the steps for right part.

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. The worst-case time complexity of this version is O(n2) and the average time complexity is O(n).

Following is the implementation of the above algorithm:

## C++

 `#include ``using` `namespace` `std;` `// picks up last element between start and end``int` `findPivot(``int` `a[], ``int` `start, ``int` `end)``{``    ``// Selecting the pivot element``    ``int` `pivot = a[end];``    ``// Initially partition-index will be at starting``    ``int` `pIndex = start;``    ``for` `(``int` `i = start; i < end; i++) {``        ``// If an element is lesser than pivot, swap it.``        ``if` `(a[i] <= pivot) {``            ``swap(a[i], a[pIndex]);``            ``// Incrementing pIndex for further swapping.``            ``pIndex++;``        ``}``    ``}``    ``// Lastly swapping or the correct position of pivot``    ``swap(a[pIndex], a[end]);``    ``return` `pIndex;``}` `// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit``// Picks up random pivot element between start and end``int` `findRandomPivot(``int` `arr[], ``int` `start, ``int` `end)``{``    ``int` `n = end - start + 1;``    ``// Selecting the random pivot index``    ``int` `pivotInd = random() % n;``    ``swap(arr[end], arr[start + pivotInd]);``    ``int` `pivot = arr[end];``    ``// initialising pivoting point to start index``    ``pivotInd = start;``    ``for` `(``int` `i = start; i < end; i++) {``        ``// If an element is lesser than pivot, swap it.``        ``if` `(arr[i] <= pivot) {``            ``swap(arr[i], arr[pivotInd]);``            ``// Incrementing pivotIndex for further swapping.``            ``pivotInd++;``        ``}``    ``}` `    ``// Lastly swapping or the correct position of pivot``    ``swap(arr[pivotInd], arr[end]);``    ``return` `pivotInd;``}``// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit` `void` `SmallestLargest(``int` `a[], ``int` `low, ``int` `high, ``int` `k,``                     ``int` `n)``{``    ``if` `(low == high)``        ``return``;``    ``else` `{``        ``int` `pivotIndex = findRandomPivot(a, low, high);``        ``if` `(k == pivotIndex) {``            ``cout << k << ``" smallest elements are : "``;``            ``for` `(``int` `i = 0; i < pivotIndex; i++)``                ``cout << a[i] << ``"  "``;``            ``cout << endl;``            ``cout << k << ``" largest elements are : "``;``            ``for` `(``int` `i = (n - pivotIndex); i < n; i++)``                ``cout << a[i] << ``"  "``;``        ``}` `        ``else` `if` `(k < pivotIndex)``            ``SmallestLargest(a, low, pivotIndex - 1, k, n);``        ``else` `if` `(k > pivotIndex)``            ``SmallestLargest(a, pivotIndex + 1, high, k, n);``    ``}``}` `// Driver Code``int` `main()``{``    ``int` `a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };``    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]);``    ``int` `low = 0;``    ``int` `high = n - 1;``    ``// Lets assume k is 3``    ``int` `k = 3;``    ``// Function Call``    ``SmallestLargest(a, low, high, k, n);``    ``return` `0;``}` `// This code is contributed by Sania Kumari Gupta`

## C

 `#include ``#include ` `// This function swaps values pointed by xp and yp``void` `swap(``int``* xp, ``int``* yp)``{``    ``int` `temp = *xp;``    ``*xp = *yp;``    ``*yp = temp;``}` `// picks up last element between start and end``int` `findPivot(``int` `a[], ``int` `start, ``int` `end)``{``    ``// Selecting the pivot element``    ``int` `pivot = a[end];``    ``// Initially partition-index will be at starting``    ``int` `pIndex = start;``    ``for` `(``int` `i = start; i < end; i++) {``        ``// If an element is lesser than pivot, swap it.``        ``if` `(a[i] <= pivot) {``            ``swap(&a[i], &a[pIndex]);``            ``// Incrementing pIndex for further swapping.``            ``pIndex++;``        ``}``    ``}` `    ``// Lastly swapping or the correct position of pivot``    ``swap(&a[pIndex], &a[end]);``    ``return` `pIndex;``}` `// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit``// Picks up random pivot element between start and end``int` `findRandomPivot(``int` `arr[], ``int` `start, ``int` `end)``{``    ``int` `n = end - start + 1;``    ``// Selecting the random pivot index``    ``int` `pivotInd = random() % n;``    ``swap(&arr[end], &arr[start + pivotInd]);``    ``int` `pivot = arr[end];``    ``// initialising pivoting point to start index``    ``pivotInd = start;``    ``for` `(``int` `i = start; i < end; i++) {``        ``// If an element is lesser than pivot, swap it.``        ``if` `(arr[i] <= pivot) {``            ``swap(&arr[i], &arr[pivotInd]);``            ``// Incrementing pivotIndex for further swapping.``            ``pivotInd++;``        ``}``    ``}` `    ``// Lastly swapping or the correct position of pivot``    ``swap(&arr[pivotInd], &arr[end]);``    ``return` `pivotInd;``}``// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit` `void` `SmallestLargest(``int` `a[], ``int` `low, ``int` `high, ``int` `k,``                     ``int` `n)``{``    ``if` `(low == high)``        ``return``;``    ``else` `{``        ``int` `pivotIndex = findRandomPivot(a, low, high);``        ``if` `(k == pivotIndex) {``            ``printf``(``"%d smallest elements are : "``, k);``            ``for` `(``int` `i = 0; i < pivotIndex; i++)``                ``printf``(``"%d "``, a[i]);``            ``printf``(``"\n"``);``            ``printf``(``"%d largest elements are : "``, k);``            ``for` `(``int` `i = (n - pivotIndex); i < n; i++)``                ``printf``(``"%d "``, a[i]);``        ``}` `        ``else` `if` `(k < pivotIndex)``            ``SmallestLargest(a, low, pivotIndex - 1, k, n);``        ``else` `if` `(k > pivotIndex)``            ``SmallestLargest(a, pivotIndex + 1, high, k, n);``    ``}``}` `// Driver Code``int` `main()``{``    ``int` `a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };``    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]);``    ``int` `low = 0;``    ``int` `high = n - 1;``    ``// Lets assume k is 3``    ``int` `k = 3;``    ``// Function Call``    ``SmallestLargest(a, low, high, k, n);``    ``return` `0;``}` `// This code is contributed by Sania Kumari Gupta`

## Java

 `import` `java.util.*;` `class` `GFG{` `  ``//picks up last element between start and end``  ``static` `int` `findPivot(``int` `a[], ``int` `start, ``int` `end)``  ``{` `    ``// Selecting the pivot element``    ``int` `pivot = a[end];` `    ``// Initially partition-index will be``    ``// at starting``    ``int` `pIndex = start;` `    ``for` `(``int` `i = start; i < end; i++) {` `      ``// If an element is lesser than pivot, swap it.``      ``if` `(a[i] <= pivot) {``        ``int` `temp =a[i];``        ``a[i]= a[pIndex];``        ``a[pIndex]  = temp;`  `        ``// Incrementing pIndex for further``        ``// swapping.``        ``pIndex++;``      ``}``    ``}` `    ``// Lastly swapping or the``    ``// correct position of pivot``    ``int` `temp = a[pIndex];``    ``a[pIndex] = a[end];``    ``a[end] = temp;``    ``return` `pIndex;``  ``}`  `  ``//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit``  ``//Picks up random pivot element between start and end``  ``static` `int` `findRandomPivot(``int` `arr[], ``int` `start, ``int` `end)``  ``{``    ``int` `n = end - start + ``1``;``    ``// Selecting the random pivot index``    ``int` `pivotInd = (``int``) ((Math.random()*``1000000``)%n);``    ``int` `temp = arr[end];``    ``arr[end] = arr[start+pivotInd];``    ``arr[start+pivotInd] = temp;``    ``int` `pivot = arr[end];``    ``//initialising pivoting point to start index``    ``pivotInd = start;``    ``for` `(``int` `i = start; i < end; i++) {` `      ``// If an element is lesser than pivot, swap it.``      ``if` `(arr[i] <= pivot) {``        ``int` `temp1 = arr[i];``        ``arr[i]= arr[pivotInd];``        ``arr[pivotInd] = temp1;` `        ``// Incrementing pivotIndex for further``        ``// swapping.``        ``pivotInd++;``      ``}``    ``}` `    ``// Lastly swapping or the``    ``// correct position of pivot``    ``int` `tep = arr[pivotInd];``    ``arr[pivotInd] =  arr[end];``    ``arr[end] = tep;``    ``return` `pivotInd;``  ``}``  ``//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit` `  ``static` `void` `SmallestLargest(``int` `a[], ``int` `low, ``int` `high, ``int` `k,``                              ``int` `n)``  ``{``    ``if` `(low == high)``      ``return``;``    ``else` `{``      ``int` `pivotIndex = findRandomPivot(a, low, high);` `      ``if` `(k == pivotIndex) {``        ``System.out.print(k+ ``" smallest elements are : "``);``        ``for` `(``int` `i = ``0``; i < pivotIndex; i++)``          ``System.out.print(a[i]+ ``"  "``);` `        ``System.out.println();` `        ``System.out.print(k+ ``" largest elements are : "``);``        ``for` `(``int` `i = (n - pivotIndex); i < n; i++)``          ``System.out.print(a[i]+ ``"  "``);``      ``}` `      ``else` `if` `(k < pivotIndex)``        ``SmallestLargest(a, low, pivotIndex - ``1``, k, n);` `      ``else` `if` `(k > pivotIndex)``        ``SmallestLargest(a, pivotIndex + ``1``, high, k, n);``    ``}``  ``}` `  ``// 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` `low = ``0``;``    ``int` `high = n - ``1``;` `    ``// Lets assume k is 3``    ``int` `k = ``3``;` `    ``// Function Call``    ``SmallestLargest(a, low, high, k, n);``  ``}``}` `// This code is contributed by Rajput-Ji`

## Python3

 `# Python program to implement above approach` `# picks up last element between start and end``import` `random` `def` `findPivot(a, start, end):`` ` `    ``# Selecting the pivot element``    ``pivot ``=` `a[end]` `    ``# Initially partition-index will be``    ``# at starting``    ``pIndex ``=` `start` `    ``for` `i ``in` `range``(start,end):` `        ``# If an element is lesser than pivot, swap it.``        ``if` `(a[i] <``=` `pivot):``            ``a[i],a[pIndex] ``=` `a[pIndex],a[i]` `            ``# Incrementing pIndex for further``            ``# swapping.``            ``pIndex ``+``=` `1``      ` ` ` `    ``# Lastly swapping or the``    ``# correct position of pivot``    ``a[end],a[pIndex] ``=` `a[pIndex],a[end]``    ``return` `pIndex`` ` ` ` `#THIS PART OF CODE IS CONTRIBUTED BY - rjrachit``#Picks up random pivot element between start and end``def` `findRandomPivot(arr, start, end):``  ` `    ``n ``=` `end ``-` `start ``+` `1``    ``# Selecting the random pivot index``    ``pivotInd ``=`  `(``int``((random.random()``*``1000000``))``%``n)``    ``arr[end],arr[start``+``pivotInd] ``=` `arr[start``+``pivotInd],arr[end]``    ``pivot ``=` `arr[end]``    ` `    ``#initialising pivoting poto start index``    ``pivotInd ``=` `start``    ``for` `i ``in` `range``(start,end):` `        ``# If an element is lesser than pivot, swap it.``        ``if` `(arr[i] <``=` `pivot):``            ``arr[i],arr[pivotInd] ``=` `arr[pivotInd],arr[i]` `            ``# Incrementing pivotIndex for further``            ``# swapping.``            ``pivotInd ``+``=` `1``        `  `    ``# Lastly swapping or the``    ``# correct position of pivot``    ``arr[pivotInd],arr[end] ``=` `arr[end],arr[pivotInd]``    ``return` `pivotInd`  `def` `SmallestLargest(a, low, high, k, n):``    ``if` `(low ``=``=` `high):``        ``return``    ``else``:``        ``pivotIndex ``=` `findRandomPivot(a, low, high)`` ` `        ``if` `(k ``=``=` `pivotIndex):``            ``print``(``str``(k)``+` `" smallest elements are :"``,end``=``" "``)``            ``for` `i ``in` `range``(pivotIndex):``                ``print``(a[i],end ``=` `"  "``)`` ` `            ``print``()`` ` `            ``print``(``str``(k)``+` `" largest elements are :"``,end``=``" "``)``            ``for` `i ``in` `range``(n ``-` `pivotIndex,n):``                ``print``(a[i],end``=``"  "``)`` ` `        ``elif` `(k < pivotIndex):``            ``SmallestLargest(a, low, pivotIndex ``-` `1``, k, n)`` ` `        ``elif` `(k > pivotIndex):``            ``SmallestLargest(a, pivotIndex ``+` `1``, high, k, n)``    ` `# Driver code``a ``=` `[ ``11``, ``3``, ``2``, ``1``, ``15``, ``5``, ``4``, ``45``, ``88``, ``96``, ``50``, ``45` `]``n ``=` `len``(a)`` ` `low ``=` `0``high ``=` `n ``-` `1`` ` `#  assume k is 3``k ``=` `3`` ` `# Function Call``SmallestLargest(a, low, high, k, n)` `# This code is contributed by shinjanpatra`

## C#

 `using` `System;``using` `System.Text;` `public` `class` `GFG {` `  ``// picks up last element between start and end``  ``static` `int` `findPivot(``int` `[]a, ``int` `start, ``int` `end) {` `    ``// Selecting the pivot element``    ``int` `pivot = a[end];` `    ``// Initially partition-index will be``    ``// at starting``    ``int` `pIndex = start;` `    ``for` `(``int` `i = start; i < end; i++) {` `      ``// If an element is lesser than pivot, swap it.``      ``if` `(a[i] <= pivot) {``        ``int` `temp6 = a[i];``        ``a[i] = a[pIndex];``        ``a[pIndex] = temp6;` `        ``// Incrementing pIndex for further``        ``// swapping.``        ``pIndex++;``      ``}``    ``}` `    ``// Lastly swapping or the``    ``// correct position of pivot``    ``int` `temp = a[pIndex];``    ``a[pIndex] = a[end];``    ``a[end] = temp;``    ``return` `pIndex;``  ``}` `  ``// THIS PART OF CODE IS CONTRIBUTED BY - rjrachit``  ``// Picks up random pivot element between start and end``  ``static` `int` `findRandomPivot(``int` `[]arr, ``int` `start, ``int` `end) {``    ``int` `n = end - start + 1;``    ` `    ``// Selecting the random pivot index``    ``Random _random = ``new` `Random();``    ``var` `randomNumber = _random.Next(0, n); ``    ``int` `pivotInd = randomNumber;``    ``int` `temp = arr[end];``    ``arr[end] = arr[start + pivotInd];``    ``arr[start + pivotInd] = temp;``    ``int` `pivot = arr[end];``    ` `    ``// initialising pivoting point to start index``    ``pivotInd = start;``    ``for` `(``int` `i = start; i < end; i++) {` `      ``// If an element is lesser than pivot, swap it.``      ``if` `(arr[i] <= pivot) {``        ``int` `temp1 = arr[i];``        ``arr[i] = arr[pivotInd];``        ``arr[pivotInd] = temp1;` `        ``// Incrementing pivotIndex for further``        ``// swapping.``        ``pivotInd++;``      ``}``    ``}` `    ``// Lastly swapping or the``    ``// correct position of pivot``    ``int` `tep = arr[pivotInd];``    ``arr[pivotInd] = arr[end];``    ``arr[end] = tep;``    ``return` `pivotInd;``  ``}` `  ``static` `void` `SmallestLargest(``int` `[]a, ``int` `low, ``int` `high, ``int` `k, ``int` `n) {``    ``if` `(low == high)``      ``return``;``    ``else` `{``      ``int` `pivotIndex = findRandomPivot(a, low, high);` `      ``if` `(k == pivotIndex) {``        ``Console.Write(k + ``" smallest elements are : "``);``        ``for` `(``int` `i = 0; i < pivotIndex; i++)``          ``Console.Write(a[i] + ``"  "``);` `        ``Console.WriteLine();` `        ``Console.Write(k + ``" largest elements are : "``);``        ``for` `(``int` `i = (n - pivotIndex); i < n; i++)``          ``Console.Write(a[i] + ``"  "``);``      ``}` `      ``else` `if` `(k < pivotIndex)``        ``SmallestLargest(a, low, pivotIndex - 1, k, n);` `      ``else` `if` `(k > pivotIndex)``        ``SmallestLargest(a, pivotIndex + 1, high, k, n);``    ``}``  ``}` `  ``// 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` `low = 0;``    ``int` `high = n - 1;` `    ``// Lets assume k is 3``    ``int` `k = 3;` `    ``// Function Call``    ``SmallestLargest(a, low, high, k, n);``  ``}``}` `// This code is contributed by Rajput-Ji`

## Javascript

 ``

Output

```3 smallest elements are : 3  2  1
3 largest elements are : 96  50  88  ```

Time Complexity: O(nlogn)
Auxiliary Space: O(1)

Method 8(Using priority queue STL library):
In this approach, we can efficiently print the k largest/smallest elements of an array using a priority queue in O(n*log(k)) time complexity. First, we push k elements into the priority queue from the array. From there on, after every insertion of an array element, we will pop the element at the top of priority_queue. In the case of the k largest element, the priority_queue will be in increasing order, and thus top most element will be the smallest so we are removing it. Similarly, in the case of the k smallest element, the priority_queue is in decreasing order and hence the top most element is the largest one so we will remove it. In this fashion whole array is traversed and the priority queue of size k is printed which contains k largest/smallest elements.

Below is the implementation of the above approach:

## C++

 `// C++ code for k largest/ smallest elements in an array``#include ``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<& v, ``int` `N, ``int` `K)``{``    ``// Implementation using``    ``// a Priority Queue``    ``priority_queue<``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 smallest element``    ``while``(!pq.empty())``    ``{``        ``cout << pq.top() <<``" "``;``        ``pq.pop();``    ``}``    ` `}` `// 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<

## Java

 `// Java code for k largest/ smallest 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 pq``            ``= ``new` `PriorityQueue();` `        ``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();``    ``}` `    ``// Function to find k smallest array element``    ``static` `void` `kSmallest(``int` `a[], ``int` `n, ``int` `k)``    ``{``        ``// Implementation using``        ``// a Priority Queue``        ``PriorityQueue pq``            ``= ``new` `PriorityQueue(``                ``Collections.reverseOrder());` `        ``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();``        ``}``    ``}` `    ``// 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);``        ``System.out.print(k + ``" smallest elements are : "``);``        ``// Function Call``        ``kSmallest(a, n, k);``    ``}``}` `// This code is contributed by Aarti_Rathi`

## Python3

 `# Python code for k largest/ smallest 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``()`  `# Function to find k smallest array element``def` `kSmalest(v,  N, K):` `    ``# Implementation using``    ``# a Priority Queue``    ``pq ``=` `[]` `    ``for` `i ``in` `range``(N):` `        ``# Insert elements into``        ``# the priority queue``        ``heapq.heappush(pq, ``-``1``*``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)``*``-``1``, 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)``print``(k, ``" smallest elements are : "``, end``=``'')``kSmalest(arr, n, k)`  `# This code is contributed by Abhijeet Kumar(abhijeet19403)`

Output

```3 largest elements are : 50 88 96
3 smallest elements are : 3 2 1 ```

Time Complexity: O(n*log(k))
Auxiliary Space: O(k)

Method 9(Creating a BST and Getting K greatest Elements):

In this approach, we will create a Binary Search Tree and then we will print K greatest elements of it.

## C++

 `#include ``using` `namespace` `std;` `struct` `Node{``    ``int` `data;``    ``struct` `Node *left;``    ``struct` `Node *right;``};` `class` `Tree{``    ``public``:``        ``Node *root = NULL;``        ``void` `addNode(``int` `data){``            ``Node *newNode = ``new` `Node();``            ``newNode->data = data;``            ``if` `(!root){``                ``root = newNode;``            ``}``            ``else``{``                ``Node *cur = root;``                ``while` `(cur){``                    ``if` `(cur->data > data){``                        ``if` `(cur->left){``                            ``cur = cur->left;``                        ``}``                        ``else``{``                            ``cur->left = newNode;``                            ``return``;``                        ``}``                    ``}``                    ``else``{``                        ``if` `(cur->right){``                            ``cur = cur->right;``                        ``}``                        ``else``{``                            ``cur->right = newNode;``                            ``return``;``                        ``}``                    ``}``                ``}``            ``}``        ``}``        ``void` `printGreatest(``int` `&K, vector<``int``> &sol, Node* node){``            ``if` `(!node || K == 0)  ``return``;``            ``printGreatest(K, sol, node->right);``            ``if` `(K <= 0) ``return``;``            ``sol.push_back(node->data);``            ``K--;``            ``printGreatest(K, sol, node->left);``        ``}``};` `class` `Solution{``public``:``    ` `    ``vector<``int``> kLargest(``int` `arr[], ``int` `n, ``int` `k) {``        ``vector<``int``> sol;``        ``Tree tree = Tree();``        ``for` `(``int` `i = 0; i < n; i++){``            ``tree.addNode(arr[i]);``        ``}``        ``tree.printGreatest(k, sol, tree.root);``        ``return` `sol;``    ``}` `};`  `int` `main() {``      ``int` `n = 5, k = 2;``      ``int` `arr[] = {12, 5, 787, 1, 23};``      ``Solution ob;``      ``auto` `ans = ob.kLargest(arr, n, k);``      ``cout << ``"Top "` `<< k << ``" Elements: "``;``    ``for` `(``auto` `x : ans) {``      ``cout << x << ``" "``;``    ``}``    ``cout << ``"\n"``;``    ``return` `0;``}`

Output

`Top 2 Elements: 787 23 `

Please write comments if you find any of the above explanations/algorithms incorrect, or find better ways to solve the same problem.
References:
http://en.wikipedia.org/wiki/Selection_algorithm

My Personal Notes arrow_drop_up