Open App

Class 8 Exam > Class 8 Notes > K’th Largest Element in an array

K’th Largest Element in an array - Class 8 PDF Download

k largest(or smallest) elements in an array

Question: 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.

Method 1 (Use Bubble k times)
Thanks to Shailendra for suggesting this approach.

Modify Bubble Sort to run the outer loop at most k times.
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]

Store the first k elements in a temporary array temp[0..k-1].
Find the smallest element in temp[], let the smallest element be min.
(i) 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.
(ii) Then, determine the new min from temp[]. O(k)
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)

Sort the elements in descending order in O(n*log(n))
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 <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 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 article is contributed by Chhavi

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

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

<?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
?>

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>

Output

50 30 23

Time complexity: O(n*log(n))
Method 4 (Use Max Heap)

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

Time complexity: O(n + k*log(n))
Method 5(Use Order Statistics)

Use an order statistic algorithm to find the kth largest element.
Use QuickSort Partition algorithm to partition around the kth largest number O(n).
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))
Method 6 (Use Min Heap)
This method is mainly an optimization of method 1. Instead of using temp[] array, use Min Heap.

Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k*log(k))
For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
(i) If the element is greater than the root then make it root and call heapify for MH
(ii) Else ignore it.
// The step 2 is O((n-k)*log(k))
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 <iostream>
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<Integer> 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

def FirstKelements(arr,size,k):

# Creating Min Heap for given
# array with only k elements
# Create min heap with priority queue
minHeap = []
for i in range(k):
minHeap.append(arr[i])

# Loop For each element in array
# after the kth element
for i in range(k, size):
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.pop(0)
minHeap.append(arr[i])

# 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)

# This code is contributed by avanitrachhadiya2155

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

<script>
function FirstKelements(arr , size , k) {

// Creating Min Heap for given
// array with only k elements
// Create min heap with priority queue
var minHeap = [];
for (var i = 0; i < k; i++) {
minHeap.push(arr[i]);
}

// Loop For each element in array
// after the kth element
for (var i = k; i < size; i++) {
minHeap.sort((a,b)=>a-b);

// If current element is smaller
// than minimum ((top element of
// the minHeap) element, do nothing
// and continue to next element
if (minHeap[minHeap.length-3] > 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.reverse();
minHeap.pop();
minHeap.reverse();
minHeap.push(arr[i]);
}
}

// Now min heap contains k maximum
// elements, Iterate and print
for (var iterator of minHeap) {
document.write(iterator + " ");
}
}

// Driver code
var arr = [11, 3, 2, 1, 15, 5, 4,
45, 88, 96, 50, 45];
var size = arr.length;

// Size of Min Heap
var k = 3;
FirstKelements(arr, size, k);

// This code is contributed by gauravrajput1
</script>

Output

50 88 96

Method 7(Using Quick Sort partitioning algorithm):

Choose a pivot number.
if K is lesser than the pivot_Index then repeat the step.
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)
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 <bits/stdc++.h>
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;
}

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

<script>
// JavaScript code to implement the approach

//picks up last element between start and end
function findPivot( a, start, end)
{

// Selecting the pivot element
let pivot = a[end];

// Initially partition-index will be
// at starting
let pIndex = start;

for (let i = start; i < end; i++) {

// If an element is lesser than pivot, swap it.
if (a[i] <= pivot) {
let temp =a[i];
a[i]= a[pIndex];
a[pIndex] = temp;


// Incrementing pIndex for further
// swapping.
pIndex++;
}
}

// Lastly swapping or the
// correct position of pivot
let 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
function findRandomPivot(arr, start, end)
{
let n = end - start + 1;
// Selecting the random pivot index
let pivotInd = (parseInt((Math.random()*1000000))%n);
let temp = arr[end];
arr[end] = arr[start+pivotInd];
arr[start+pivotInd] = temp;
let pivot = arr[end];
//initialising pivoting point to start index
pivotInd = start;
for (let i = start; i < end; i++) {

// If an element is lesser than pivot, swap it.
if (arr[i] <= pivot) {
let temp1 = arr[i];
arr[i]= arr[pivotInd];
arr[pivotInd] = temp1;

// Incrementing pivotIndex for further
// swapping.
pivotInd++;
}
}

// Lastly swapping or the
// correct position of pivot
let tep = arr[pivotInd];
arr[pivotInd] = arr[end];
arr[end] = tep;
return pivotInd;
}
//THIS PART OF CODE IS CONTRIBUTED BY - rjrachit

function SmallestLargest( a, low, high, k,
n)
{
if (low == high)
return;
else {
let pivotIndex = findRandomPivot(a, low, high);

if (k == pivotIndex) {
document.write(k+ " smallest elements are : ");
for (let i = 0; i < pivotIndex; i++)
document.write(a[i]+ " ");

document.write("<br/>");

document.write(k+ " largest elements are : ");
for (let i = (n - pivotIndex); i < n; i++)
document.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

let a = [ 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 ];
let n = a.length;

let low = 0;
let high = n - 1;

// Lets assume k is 3
let k = 3;

// Function Call
SmallestLargest(a, low, high, k, n);

// This code is contributed by sanjoy_62.
</script>

Output

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

The document K’th Largest Element in an array - Class 8 is a part of Class 8 category.

All you need of Class 8 at this link: Class 8

About this Document

Sep 10, 2025 Last updated

Related Exams

Class 8

Document Description: K’th Largest Element in an array for Class 8 2025 is part of Class 8 preparation. The notes and questions for K’th Largest Element in an array have been prepared according to the Class 8 exam syllabus. Information about K’th Largest Element in an array covers topics like k largest(or smallest) elements in an array, C++  and K’th Largest Element in an array Example, for Class 8 2025 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for K’th Largest Element in an array.

Introduction of K’th Largest Element in an array in English is available as part of our Class 8 preparation & K’th Largest Element in an array in Hindi for Class 8 courses. Download more important topics, notes, lectures and mock test series for Class 8 Exam by signing up for free. Class 8: K’th Largest Element in an array - Class 8

Description

Full syllabus notes, lecture & questions for K’th Largest Element in an array - Class 8 - Class 8 | Plus excerises question with solution to help you revise complete syllabus | Best notes, free PDF download

Information about K’th Largest Element in an array

In this doc you can find the meaning of K’th Largest Element in an array defined & explained in the simplest way possible. Besides explaining types of K’th Largest Element in an array theory, EduRev gives you an ample number of questions to practice K’th Largest Element in an array tests, examples and also practice Class 8 tests.

Download as PDF

Top Courses for Class 8

View all courses for Class 8

Free

Important questions

Sample Paper

study material

K’th Largest Element in an array - Class 8

MCQs

K’th Largest Element in an array - Class 8

Previous Year Questions with Solutions

Semester Notes

Summary

Exam

practice quizzes

pdf

past year papers

Viva Questions

K’th Largest Element in an array - Class 8

Objective type Questions

mock tests for examination

Extra Questions

video lectures

ppt

shortcuts and tricks

;

Additional Information about K’th Largest Element in an array for Class 8 Preparation

K’th Largest Element in an array Free PDF Download

The K’th Largest Element in an array is an invaluable resource that delves deep into the core of the Class 8 exam. These study notes are curated by experts and cover all the essential topics and concepts, making your preparation more efficient and effective. With the help of these notes, you can grasp complex subjects quickly, revise important points easily, and reinforce your understanding of key concepts. The study notes are presented in a concise and easy-to-understand manner, allowing you to optimize your learning process. Whether you're looking for best-recommended books, sample papers, study material, or toppers' notes, this PDF has got you covered. Download the K’th Largest Element in an array now and kickstart your journey towards success in the Class 8 exam.

Importance of K’th Largest Element in an array

The importance of K’th Largest Element in an array cannot be overstated, especially for Class 8 aspirants. This document holds the key to success in the Class 8 exam. It offers a detailed understanding of the concept, providing invaluable insights into the topic. By knowing the concepts well in advance, students can plan their preparation effectively. Utilize this indispensable guide for a well-rounded preparation and achieve your desired results.

K’th Largest Element in an array Notes

K’th Largest Element in an array Notes offer in-depth insights into the specific topic to help you master it with ease. This comprehensive document covers all aspects related to K’th Largest Element in an array. It includes detailed information about the exam syllabus, recommended books, and study materials for a well-rounded preparation. Practice papers and question papers enable you to assess your progress effectively. Additionally, the paper analysis provides valuable tips for tackling the exam strategically. Access to Toppers' notes gives you an edge in understanding complex concepts. Whether you're a beginner or aiming for advanced proficiency, K’th Largest Element in an array Notes on EduRev are your ultimate resource for success.

K’th Largest Element in an array Class 8 Questions

The "K’th Largest Element in an array Class 8 Questions" guide is a valuable resource for all aspiring students preparing for the Class 8 exam. It focuses on providing a wide range of practice questions to help students gauge their understanding of the exam topics. These questions cover the entire syllabus, ensuring comprehensive preparation. The guide includes previous years' question papers for students to familiarize themselves with the exam's format and difficulty level. Additionally, it offers subject-specific question banks, allowing students to focus on weak areas and improve their performance.

Study K’th Largest Element in an array on the App

Students of Class 8 can study K’th Largest Element in an array alongwith tests & analysis from the EduRev app, which will help them while preparing for their exam. Apart from the K’th Largest Element in an array, students can also utilize the EduRev App for other study materials such as previous year question papers, syllabus, important questions, etc. The EduRev App will make your learning easier as you can access it from anywhere you want. The content of K’th Largest Element in an array is prepared as per the latest Class 8 syllabus.

Education Revolution

Signup on EduRev and stay on top of your study goals

Signup with Google

10M+ students crushing their study goals daily