Print K largest(or smallest) elements in an array - GeeksforGeeks (2024)

// 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 codeint 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 code for k largest elements in an array#include <stdio.h>#include <stdlib.h>// Compare function for qsortint 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 codeint 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 code for k largest elements in an arrayimport 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

''' 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 codearr = [1, 23, 12, 9, 30, 2, 50]# n = len(arr)k = 3kLargest(arr, k)# This code is contributed by shreyanshi_arun.

// C# code for k largest elements in an arrayusing 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

<script>// JavaScript code for k largest// elements in an arrayfunction 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 code for k largest // elements in an arrayfunction 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?>

// 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 searchint 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 arrayvoid 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 codeint 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

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

# Python code to implement the binary search approach# Function to find the Kth largest element in the array using binary searchdef 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 arraydef 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 codeif __name__ == '__main__': arr = [12, 5, 787, 1, 23] n = len(arr) k = 2 printKLargest(arr, n, k)# This code is contributed by Susobhan Akhuli

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); } }}

// Function to find the Kth largest element in the array using binary searchfunction 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 arrayfunction 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 codeconst arr = [12, 5, 787, 1, 23];const k = 2;printKLargest(arr, k);

// 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 codeint 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;}

#include <stdio.h>// Function to swap two integersvoid 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 arrayint 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 methodvoid 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;}

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(); }}

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 idef 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()

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(); }}

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(); }}

// C++ code for k largest elements in an array#include <bits/stdc++.h>using namespace std;// Function to find k largest array elementvoid 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 programint 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 code for k largest elements in an arrayimport 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); }};

# Python code for k largest elements in an arrayimport heapq# Function to find k largest array elementdef 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 arrayarr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45]# Size of arrayn = len(arr)k = 3print(k, " largest elements are : ", end='')kLargest(arr, n, k)

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);  }}

// Function to find k largest array elementfunction 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 arrayconst arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45];// Size of arrayconst n = arr.length;const k = 3;console.log(`${k} largest elements are: `);kLargest(arr, n, k);// This code is contributed by adityamaharshi21