Given an array and a number K where K is smaller than the size of the array. Find the K’th smallest element in the given array. Given that all array elements are distinct. Examples: Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 3
Output: 7 Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 4
Output: 10
We have discussed a similar problem to print k largest elements. K’th smallest element in an unsorted array using sorting:Sort the given array and return the element at index K-1 in the sorted array.
Follow the given steps to solve the problem: - Sort the input array in the increasing order
- Return the element at the
K-1 index (0 – Based indexing) in the sorted array
Below is the Implementation of the above approach: C#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int kthSmallest(int arr[], int N, int K)
{
qsort(arr, N, sizeof(int), cmpfunc);
return arr[K - 1];
}
int main()
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]), K = 2;
printf("K'th smallest element is %d",
kthSmallest(arr, N, K));
return 0;
}
C++#include <bits/stdc++.h>
using namespace std;
int kthSmallest(int arr[], int N, int K)
{
sort(arr, arr + N);
return arr[K - 1];
}
int main()
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]), K = 2;
cout << "K'th smallest element is "
<< kthSmallest(arr, N, K);
return 0;
}
Javaimport java.util.Arrays;
import java.util.Collections;
class GFG {
public static int kthSmallest(Integer[] arr, int K)
{
Arrays.sort(arr);
return arr[K - 1];
}
public static void main(String[] args)
{
Integer arr[] = new Integer[] { 12, 3, 5, 7, 19 };
int K = 2;
System.out.print("K'th smallest element is "
+ kthSmallest(arr, K));
}
}
Python3def kthSmallest(arr, N, K):
arr.sort()
return arr[K-1]
if __name__ == '__main__':
arr = [12, 3, 5, 7, 19]
N = len(arr)
K = 2
print("K'th smallest element is",
kthSmallest(arr, N, K))
C#using System;
class GFG {
public
static int kthSmallest(int[] arr, int K)
{
Array.Sort(arr);
return arr[K - 1];
}
public static void Main()
{
int[] arr = new int[] { 12, 3, 5, 7, 19 };
int K = 2;
Console.Write("K'th smallest element"
+ " is " + kthSmallest(arr, K));
}
}
PHP<?php
function
kthSmallest($arr, $N, $K)
{
sort($arr);
return $arr[$K - 1];
}
$arr = array(12, 3, 5, 7, 19);
$N =count($arr);
$K = 2;
echo "K'th smallest element is ", kthSmallest($arr, $N, $K);
?>
Javascriptfunction
kthSmallest(arr, N, K)
{
arr.sort((a,b) => a-b);
return arr[K - 1];
}
let arr = [12, 3, 5, 7, 19];
let N = arr.length, K = 2;
document.write("K'th smallest element is " + kthSmallest(arr, N, K));
Output K'th smallest element is 5 Time Complexity: O(N log N)
Auxiliary Space: O(1) K’th smallest element in an unsorted array using set data structure: Set data structure can be used to
find the kth smallest element as it stores the distinct elements in sorted order. Set can be used because it is mentioned in the question that all the elements in the array are distinct.
Follow the given steps to solve the problem: - Insert all array elements into the set
- Advance the iterator to the Kth element in the set
- Return the value of the element at which the iterator is pointing
Below
is the Implementation of the above approach: C++#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 4;
set<int> s(arr, arr + N);
set<int>::iterator itr = s.begin();
advance(itr, K - 1);
cout << *itr << "\n";
return 0;
}
Javaimport java.util.*;
class GFG {
public static void main(String[] args)
{
int[] arr = { 12, 3, 5, 7, 19 };
int N = arr.length;
int K = 4;
K--;
Set<Integer> s = new TreeSet<Integer>();
for (int i = 0; i < N; i++)
s.add(arr[i]);
Iterator<Integer> itr = s.iterator();
while (K > 0) {
itr.next();
K--;
}
System.out.println(itr.next());
}
}
Python3if __name__ == '__main__':
arr = [12, 3, 5, 7, 19]
N = len(arr)
K =
4
s = set(arr)
for itr in s:
if K == 1:
print(itr)
break
K -= 1
C#using System;
using System.Collections.Generic;
class GFG {
public static void Main()
{
int[] arr = { 12, 3, 5, 7, 19 };
int
N = arr.Length;
int K = 4;
SortedSet<int> s = new SortedSet<int>();
foreach(int i in arr) s.Add(i);
foreach(int itr in s)
{
if (K == 1) {
Console.WriteLine(itr);
break;
}
K--;
}
}
}
Time
Complexity: O(N*log N)
Auxiliary Space: O(N) K’th smallest element in an unsorted array using heap data structure:K’th smallest element in an unsorted array using Min-HeapMin-Heap can be used to find the kth smallest element, by inserting all the elements into Min-Heap and then and call extractMin()
function K times.
Follow the given steps to solve the problem: - Insert all the array elements into the Min-Heap
- Call extractMin() function K times
- Return the value obtained at the last call of extractMin() function
Below is the Implementation of the above approach: C++#include <climits>
#include <iostream>
using namespace
std;
void swap(int* x, int* y);
class MinHeap {
int* harr;
int capacity;
int heap_size;
public:
MinHeap(int a[], int size);
void MinHeapify(int i);
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int
i) { return (2 * i + 2); }
int extractMin();
int getMin() { return harr[0]; }
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
int MinHeap::extractMin()
{
if (heap_size == 0)
return
INT_MAX;
int root = harr[0];
if (heap_size > 1) {
harr[0] = harr[heap_size - 1];
MinHeapify(0);
}
heap_size--;
return root;
}
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if
(smallest != i) {
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int kthSmallest(int arr[], int N, int K)
{
MinHeap mh(arr, N);
for (int i = 0; i < K - 1; i++)
mh.extractMin();
return mh.getMin();
}
int
main()
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]), K = 2;
cout << "K'th smallest element is "
<< kthSmallest(arr, N, K);
return 0;
}
Javaimport java.util.*;
class GFG {
class MinHeap {
int[] harr;
int capacity;
int heap_size;
int parent(int i) { return
(i - 1) / 2; }
int left(int i) { return ((2 * i) + 1); }
int right(int i) { return ((2 * i) + 2); }
int getMin() { return harr[0]; }
void replaceMax(int x)
{
this.harr[0] = x;
minHeapify(0);
}
MinHeap(int
a[], int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
minHeapify(i);
i--;
}
}
int extractMin()
{
if (heap_size == 0)
return Integer.MAX_VALUE;
int root = harr[0];
if
(heap_size > 1) {
harr[0] = harr[heap_size - 1];
minHeapify(0);
}
heap_size--;
return root;
}
void minHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i) {
int t = harr[i];
harr[i] = harr[smallest];
harr[smallest] = t;
minHeapify(smallest);
}
}
};
int kthSmallest(int arr[], int N, int K)
{
MinHeap mh = new MinHeap(arr, N);
for (int i = 0; i < K - 1; i++)
mh.extractMin();
return mh.getMin();
}
public static void main(String[] args)
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = arr.length, K = 2;
GFG gfg = new GFG();
System.out.print("K'th smallest element is "
+ gfg.kthSmallest(arr, N, K));
}
}
Python3class MinHeap:
def __init__(self, a, size):
self.harr =
a
self.capacity = None
self.heap_size = size
i = int((self.heap_size - 1) / 2)
while i >= 0:
self.minHeapify(i)
i -= 1
def parent(self, i):
return (i - 1) / 2
def
left(self, i):
return 2 * i + 1
def right(self, i):
return 2 * i + 2
def getMin(self):
return self.harr[0]
def extractMin(self):
if self.heap_size == 0:
return float("inf")
root =
self.harr[0]
if self.heap_size > 1:
self.harr[0] = self.harr[self.heap_size - 1]
self.minHeapify(0)
self.heap_size -= 1
return root
def minHeapify(self, i):
l = self.left(i)
r = self.right(i)
smallest =
i
if ((l < self.heap_size) and
(self.harr[l] < self.harr[i])):
smallest = l
if ((r < self.heap_size) and
(self.harr[r] < self.harr[smallest])):
smallest = r
if smallest != i:
self.harr[i], self.harr[smallest] = (
self.harr[smallest], self.harr[i])
self.minHeapify(smallest)
def kthSmallest(arr, N, K):
mh = MinHeap(arr, N)
for i in range(K - 1):
mh.extractMin()
return mh.getMin()
if __name__ == '__main__':
arr = [12, 3, 5, 7, 19]
N = len(arr)
K = 2
print("K'th smallest element is", kthSmallest(arr, N, K))
C#using System;
public class GFG {
public class MinHeap {
int[] harr;
int heap_size;
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return ((2 * i) + 1); }
int right(int i) { return ((2 * i) + 2); }
public int getMin()
{
return
harr[0];
}
public void replaceMax(int x)
{
this.harr[0] = x;
minHeapify(0);
}
public MinHeap(int[] a, int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
minHeapify(i);
i--;
}
}
public
int extractMin()
{
if (heap_size == 0)
return Int32.MaxValue;
int root = harr[0];
if (heap_size > 1) {
harr[0] = harr[heap_size - 1];
minHeapify(0);
}
heap_size--;
return root;
}
public void minHeapify(int i)
{
int l = left(i);
int r = right(i);
int
smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i) {
int t = harr[i];
harr[i] = harr[smallest];
harr[smallest] = t;
minHeapify(smallest);
}
}
};
int kthSmallest(int[] arr, int N, int K)
{
MinHeap mh = new MinHeap(arr, N);
for (int
i = 0; i < K - 1; i++)
mh.extractMin();
return mh.getMin();
}
static public void Main()
{
int[] arr = { 12, 3, 5, 7, 19 };
int N = arr.Length, K = 2;
GFG gfg = new GFG();
Console.Write("K'th smallest element is "
+ gfg.kthSmallest(arr, N, K));
}
}
Javascriptclass MinHeap {
parent(i) {
return
(i - 1) / 2;
};
left(i) {
return ((2 * i) + 1);
};
right(i) {
return ((2 * i) + 2);
}
getMin() {
return this.harr[0];
}
replaceMax(x) {
this.harr[0] = x;
minHeapify(0);
}
constructor(a, size) {
this.heap_size = size;
this.harr = a;
let i = (this.heap_size - 1) / 2;
while (i >= 0) {
this.minHeapify(i);
i--;
}
}
extractMin() {
if (this.heap_size == 0)
return Number.MAX_SAFE_INTEGER;
let root = this.harr[0];
if (this.heap_size > 1) {
this.harr[0] = this.harr[this.heap_size - 1];
this.minHeapify(0);
}
this.heap_size--;
return
root;
}
minHeapify(i) {
let l = this.left(i);
let r = this.right(i);
let smallest = i;
if (l < this.heap_size && this.harr[l] < this.harr[i])
smallest = l;
if (r < this.heap_size && this.harr[r] < this.harr[smallest])
smallest = r;
if (smallest != i) {
let t = this.harr[i];
this.harr[i] = this.harr[smallest];
this.harr[smallest] = t;
this.minHeapify(smallest);
}
}
};
function kthSmallest(arr, N, K) {
let mh = new MinHeap(arr, N);
for (let i = 0; i < K - 1; i++)
mh.extractMin();
return mh.getMin();
}
let arr = [12, 3, 5, 7, 19];
let N = arr.length, K = 2;
document.write("K'th smallest element is " + kthSmallest(arr, N, K));
Output K'th smallest element is 5 Time complexity: O(N + K Log N).
Auxiliary Space: O(N) K’th
smallest element in an unsorted array using Max-HeapMax-Heap can be used to find the kth smallest element, by inserting first K elements into Max-Heap and then compare remaining elements with the root of the Max-Heap and if the element is less than the root then remove the root and insert this element into the heap and finally return root of the Max-Heap
Follow
the given steps to solve the problem: - Build a Max-Heap MH of the first K elements (arr[0] to arr[K-1]) of the given array.
- For each element, after the Kth element (arr[K] to arr[n-1]), compare it with the root of MH.
- If the element is less than the root then make it the root and call heapify for Max-Heap MH
- b) Else ignore it.
- Finally, the root of the MH is the Kth smallest element.
Below is the
Implementation of the above approach: C++#include <bits/stdc++.h>
using namespace std;
void swap(int* x, int* y);
class MaxHeap {
int* harr;
int capacity;
int heap_size;
public:
MaxHeap(int a[], int size);
void maxHeapify(
int i);
int parent(int
i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
int extractMax();
int getMax() { return harr[0]; }
void replaceMax(int x)
{
harr[0] = x;
maxHeapify(0);
}
};
MaxHeap::MaxHeap(int a[], int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
maxHeapify(i);
i--;
}
}
int MaxHeap::extractMax()
{
if (heap_size == 0)
return INT_MAX;
int root = harr[0];
if (heap_size > 1) {
harr[0] = harr[heap_size - 1];
maxHeapify(0);
}
heap_size--;
return root;
}
void MaxHeap::maxHeapify(int i)
{
int l = left(i);
int r = right(i);
int largest = i;
if (l < heap_size && harr[l] > harr[i])
largest = l;
if (r < heap_size && harr[r] > harr[largest])
largest = r;
if (largest != i) {
swap(&harr[i], &harr[largest]);
maxHeapify(largest);
}
}
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
int kthSmallest(int arr[], int N, int K)
{
MaxHeap mh(arr, K);
for (int i = K; i < N; i++)
if (arr[i] < mh.getMax())
mh.replaceMax(arr[i]);
return mh.getMax();
}
int main()
{
int arr[] = { 12, 3, 5, 7, 19 };
int N = sizeof(arr) / sizeof(arr[0]), K = 4;
cout << "K'th smallest element is "
<< kthSmallest(arr, N, K);
return 0;
}
Javaimport java.util.*;
class GFG {
class MaxHeap {
int[] harr;
int capacity;
int heap_size;
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2
* i + 2); }
int getMax() { return harr[0]; }
void replaceMax(int x)
{
this.harr[0] = x;
maxHeapify(0);
}
MaxHeap(int a[], int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while
(i >= 0) {
maxHeapify(i);
i--;
}
}
int extractMax()
{
if (heap_size == 0)
return Integer.MAX_VALUE;
int root = harr[0];
if (heap_size > 1) {
harr[0] = harr[heap_size - 1];
maxHeapify(0);
}
heap_size--;
return root;
}
void maxHeapify(int i)
{
int l = left(i);
int r = right(i);
int largest = i;
if (l < heap_size && harr[l] > harr[i])
largest = l;
if (r < heap_size && harr[r] > harr[largest])
largest = r;
if (largest != i) {
int t = harr[i];
harr[i] = harr[largest];
harr[largest] = t;
maxHeapify(largest);
}
}
};
int kthSmallest(int arr[], int N, int K)
{
MaxHeap mh = new MaxHeap(arr, K);
for (int i = K; i < N; i++)
if (arr[i] < mh.getMax())
mh.replaceMax(arr[i]);
return mh.getMax();
}
public static void main(String[] args)
{
int
arr[] = { 12, 3, 5, 7, 19 };
int N = arr.length, K = 4;
GFG gfg = new GFG();
System.out.print("K'th smallest element is "
+ gfg.kthSmallest(arr, N, K));
}
}
Python3class MaxHeap:
def __init__(self, a, size):
self.harr =
a
self.capacity = None
self.heap_size = size
i = int((self.heap_size - 1) / 2)
while i >= 0:
self.maxHeapify(i)
i -= 1
def parent(self, i):
return (i - 1) / 2
def
left(self, i):
return 2 * i + 1
def right(self, i):
return 2 * i + 2
def getMax(self):
return self.harr[0]
def replaceMax(self, x):
self.harr[0] = x
self.maxHeapify(0)
def
extractMin(self):
if self.heap_size == 0:
return float("inf")
root = self.harr[0]
if self.heap_size > 1:
self.harr[0] = self.harr[self.heap_size - 1]
self.maxHeapify(0)
self.heap_size -=
1
return root
def maxHeapify(self, i):
l = self.left(i)
r = self.right(i)
largest = i
if ((l < self.heap_size) and
(self.harr[l] > self.harr[i])):
largest = l
if ((r < self.heap_size) and
(self.harr[r] > self.harr[largest])):
largest =
r
if largest != i:
self.harr[i], self.harr[largest] = (
self.harr[largest], self.harr[i])
self.maxHeapify(largest)
def kthSmallest(arr, N, K):
mh = MaxHeap(arr, K)
for i in range(K, N):
if arr[i] < mh.getMax():
mh.replaceMax(arr[i])
return mh.getMax()
if __name__ == '__main__':
arr =
[12, 3, 5, 7, 19]
N = len(arr)
K = 4
print("K'th smallest element is", kthSmallest(arr, N, K))
C#using System;
public class GFG {
public
class MaxHeap {
public
int[] harr;
public
int capacity;
public
int heap_size;
public
int
parent(int i)
{
return (i - 1) / 2;
}
public
int
left(int i)
{
return (2 * i + 1);
}
public
int
right(int i)
{
return
(2 * i + 2);
}
public
int
getMax()
{
return harr[0];
}
public
void
replaceMax(int x)
{
this.harr[0] = x;
maxHeapify(0);
}
public
MaxHeap(int[] a, int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
maxHeapify(i);
i--;
}
}
public
int
extractMax()
{
if (heap_size == 0)
return int.MaxValue;
int root = harr[0];
if (heap_size > 1) {
harr[0] = harr[heap_size - 1];
maxHeapify(0);
}
heap_size--;
return
root;
}
public
void
maxHeapify(int i)
{
int l = left(i);
int r = right(i);
int largest = i;
if (l < heap_size && harr[l] > harr[i])
largest = l;
if (r < heap_size && harr[r] > harr[largest])
largest = r;
if (largest != i) {
int t = harr[i];
harr[i] = harr[largest];
harr[largest] = t;
maxHeapify(largest);
}
}
};
int kthSmallest(int[] arr, int N, int K)
{
MaxHeap mh = new MaxHeap(arr, K);
for (int i = K; i < N; i++)
if (arr[i] < mh.getMax())
mh.replaceMax(arr[i]);
return mh.getMax();
}
public static void Main(String[] args)
{
int[] arr = { 12, 3, 5, 7, 19 };
int N = arr.Length, K = 4;
GFG gfg = new
GFG();
Console.Write("K'th smallest element is "
+ gfg.kthSmallest(arr, N, K));
}
}
Time Complexity: O(K + (N-K) * Log K)
Auxiliary Space: O(K) K’th smallest element in an unsorted array using QuickSelect:This is an optimization over method 1, if QuickSort is used as a
sorting algorithm in first step. In QuickSort, pick a pivot element, then move the pivot element to its correct position and partition the surrounding array. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot.
Follow the given steps to solve the problem: - Run quick
sort algorithm on the input array
- In this algorithm pick a pivot element and move it to it’s correct position
- Now, if index of pivot is equal to K then return the value, else if the index of pivot is greater than K, then recur for the left subarray, else recur for the right subarray
- Repeat this process until the element at index K is not found
Below is the Implementation of the above approach: C
#include <limits.h>
#include <stdio.h>
int partition(int arr[], int l, int r);
int kthSmallest(int arr[], int l, int r, int K)
{
if (K > 0 && K <= r - l + 1) {
int pos = partition(arr, l, r);
if (pos - l == K - 1)
return arr[pos];
if (pos - l > K - 1)
return kthSmallest(arr, l, pos - 1, K);
return kthSmallest(arr, pos + 1, r,
K - pos + l - 1);
}
return INT_MAX;
}
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;
}
int main()
{
int arr[] = { 12, 3, 5, 7, 4, 19, 26 };
int N = sizeof(arr) / sizeof(arr[0]), K = 3;
printf("K'th smallest element is %d",
kthSmallest(arr, 0, N - 1, K));
return 0;
}
C++#include <bits/stdc++.h>
using namespace std;
int partition(int arr[], int l, int r);
int
kthSmallest(int arr[], int l, int r, int K)
{
if (K > 0 && K <= r - l + 1) {
int pos = partition(arr, l, r);
if (pos - l == K - 1)
return arr[pos];
if (pos - l > K - 1)
return kthSmallest(arr, l, pos - 1, K);
return kthSmallest(arr, pos + 1, r,
K - pos + l - 1);
}
return INT_MAX;
}
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;
}
int main()
{
int
arr[] = { 12, 3, 5, 7, 4, 19, 26 };
int N = sizeof(arr) / sizeof(arr[0]), K = 3;
cout << "K'th smallest element is "
<< kthSmallest(arr, 0, N - 1, K);
return 0;
}
Javaimport java.util.Arrays;
import java.util.Collections;
class GFG {
public static int partition(Integer[] arr, int l, int r)
{
int x = arr[r], i = l;
for
(int j = l; j <= r - 1; j++) {
if (arr[j] <= x) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
return i;
}
public static int kthSmallest(Integer[] arr, int l,
int r, int K)
{
if (K > 0 && K <= r - l + 1) {
int pos = partition(arr, l, r);
if (pos - l == K - 1)
return arr[pos];
if (pos - l > K - 1)
return kthSmallest(arr, l, pos - 1, K);
return kthSmallest(arr, pos + 1, r,
K - pos + l - 1);
}
return Integer.MAX_VALUE;
}
public static void main(String[] args)
{
Integer arr[]
= new Integer[] { 12, 3, 5, 7, 4, 19, 26 };
int K = 3;
System.out.print(
"K'th smallest element is "
+ kthSmallest(arr, 0, arr.length - 1, K));
}
}
Python3import sys
def kthSmallest(arr, l, r, K):
if
(K > 0 and K <= r - l + 1):
pos = partition(arr, l, r)
if (pos - l == K - 1):
return arr[pos]
if (pos - l > K - 1):
return kthSmallest(arr, l, pos - 1, K)
return kthSmallest(arr, pos + 1, r,
K -
pos + l - 1)
return sys.maxsize
def partition(arr, l, r):
x = arr[r]
i = l
for j in range(l, r):
if (arr[j] <= x):
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[r] = arr[r], arr[i]
return i
if __name__ ==
"__main__":
arr = [12, 3, 5, 7, 4, 19, 26]
N = len(arr)
K = 3
print("K'th smallest element is",
kthSmallest(arr, 0, N - 1, K))
C#using System;
class GFG {
public
static int partition(int[] arr, int l, int r)
{
int x = arr[r], i = l;
int temp = 0;
for (int j = l; j <= r - 1; j++) {
if (arr[j] <= x) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
return i;
}
public static int kthSmallest(int[] arr, int l, int r,
int K)
{
if (K > 0 && K <= r - l + 1) {
int pos = partition(arr, l, r);
if (pos - l == K - 1)
return arr[pos];
if (pos - l > K - 1)
return kthSmallest(arr, l, pos - 1, K);
return kthSmallest(arr, pos + 1, r,
K - pos + l - 1);
}
return int.MaxValue;
}
public
static void Main()
{
int[] arr = { 12, 3, 5, 7, 4, 19, 26 };
int K = 3;
Console.Write(
"K'th smallest element is "
+ kthSmallest(arr, 0, arr.Length - 1, K));
}
}
Javascript function partition( arr , l , r)
{
var x = arr[r], i = l;
for (j = l; j <= r - 1; j++) {
if (arr[j] <= x) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
var temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
return i;
}
function kthSmallest( arr , l , r , k) {
if (k > 0 && k <= r - l + 1) {
var pos = partition(arr, l, r);
if (pos - l == k - 1)
return arr[pos];
if (pos - l > k - 1)
return kthSmallest(arr, l, pos - 1, k);
return kthSmallest(arr, pos + 1, r,
k - pos + l - 1);
}
return Number.MAX_VALUE;
}
var arr = [ 12, 3, 5, 7, 4, 19, 26 ];
var k = 3;
document.write("K'th smallest element is " +
kthSmallest(arr, 0, arr.length - 1, k));
Output K'th smallest element is 5 Time Complexity: O(N2) in worst case and O(N) on average
Auxiliary Space: O(1) K’th smallest element in an unsorted array using Map:This approach
is very much similar to the QuickSelect and counting sort algorithm but much easier to implement. Use a map and then map each element with its frequency. And as an ordered map would store the data in a sorted manner, so keep on adding the frequency of each element till it does not become greater than or equal to k so that the k’th element from the start can be reached i.e. the k’th smallest element.
Example: A[] = {7, 0, 25, 6, 16, 17, 0}, K = 3 Follow the given steps to solve the problem: - Store frequency of every element in a Map mp
- Now traverse over sorted elements in the Map mp and add their frequencies in a variable freq
- If at any point the value of freq is greater than or equal to K, then return the value
of iterator of Map mp
Below is the Implementation of the above approach: C++#include <bits/stdc++.h>
using namespace std;
int Kth_smallest(map<int, int> mp, int K)
{
int freq = 0;
for (auto it = mp.begin(); it != mp.end(); it++) {
freq += (it->second);
if (freq >= K)
{
return it->first;
}
}
return -1;
}
int main()
{
int N = 5;
int K = 2;
vector<int> arr = { 12, 3, 5, 7, 19 };
map<int, int> mp;
for (int i = 0; i < N; i++) {
mp[arr[i]] += 1;
}
int ans = Kth_smallest(mp, K);
cout << "The " << K << "th smallest element is " << ans
<< endl;
return 0;
}
Javaimport java.util.*;
class GFG {
static int Kth_smallest(TreeMap<Integer, Integer> mp,
int K)
{
int freq = 0;
for (Map.Entry it : mp.entrySet()) {
freq += (int)it.getValue();
if (freq >= K) {
return (int)it.getKey();
}
}
return -1;
}
public static void main(String[] args)
{
int N = 5;
int K = 2;
int[] arr = { 12, 3, 5, 7, 19 };
TreeMap<Integer, Integer> mp = new TreeMap<>();
for (int i = 0; i < N; i++) {
mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
}
int ans = Kth_smallest(mp, K);
System.out.println(
"The " + K + "th smallest element is " + ans);
}
}
Python3def Kth_smallest(mp, K):
freq = 0
for it in sorted(mp.keys()):
freq += mp[it]
if freq >= K:
return it
return -1
if __name__ ==
"__main__":
N = 5
K = 2
arr = [12, 3, 5, 7, 19]
mp = {}
for i in range(N):
if arr[i] in mp:
mp[arr[i]] = mp[arr[i]] + 1
else:
mp[arr[i]] =
1
ans = Kth_smallest(mp, K)
print("The ", K, "th smallest element is ", ans)
C#using System;
using System.Collections;
using System.Collections.Generic;
public class GFG {
static int Kth_smallest(SortedDictionary<int, int> mp,
int K)
{
int freq = 0;
foreach(var it in mp)
{
freq += (int)it.Value;
if (freq >= K) {
return (int)it.Key;
}
}
return -1;
}
public static void Main(String[] args)
{
int N = 5;
int K = 2;
int[] arr = { 12, 3, 5, 7, 19 };
SortedDictionary<int, int> mp
= new
SortedDictionary<int, int>();
for (int i = 0; i < N; i++) {
mp.Add(arr[i], mp.ContainsKey(arr[i])
? mp[arr[i]] + 1
: 1);
}
int ans = Kth_smallest(mp, K);
Console.WriteLine(
"The " + K + "th smallest element is " + ans);
}
}
Time Complexity: O(N log N)
Auxiliary Space: O(N) K’th
smallest element in an unsorted array using Priority Queue:To find the Kth minimum element in an array, insert the elements into the priority queue until the size of it is less than K, and then compare remaining elements with the root of the priority queue and if the element is less than the root then remove the root and insert this element into the priority queue and finally return root of the priority queue
Follow the given steps
to solve the problem: - Build a priority queue of the first K elements (arr[0] to arr[K-1]) of the given array.
- For each element, after the Kth element (arr[K] to arr[n-1]), compare it with the root of priority queue.
- If the element is less than the root then remove the root and insert this element into the priority queue
- b) Else ignore it.
- Finally, the root of the priority queue is the Kth smallest element.
Below
is the Implementation of the above approach: C++#include <bits/stdc++.h>
using namespace std;
int kthSmallest(int arr[], int N, int K)
{
priority_queue<int> pq;
for (int i = 0; i < K; i++) {
pq.push(arr[i]);
}
for (int i = K; i < N; i++) {
if (arr[i] < pq.top()) {
pq.pop();
pq.push(arr[i]);
}
}
return pq.top();
}
int main()
{
int N = 10;
int arr[N] = { 10, 5, 4, 3, 48, 6, 2, 33, 53, 10 };
int K = 4;
cout << "Kth Smallest Element is: "
<< kthSmallest(arr, N, K);
}
Javaimport java.util.*;
class MinHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer number1, Integer number2)
{
int
value = number1.compareTo(number2);
if (value > 0) {
return -1;
}
else if (value < 0) {
return 1;
}
else {
return 0;
}
}
}
class GFG {
static int kthSmallest(int[] v, int N, int K)
{
PriorityQueue<Integer> heap1
= new PriorityQueue<Integer>(
new MinHeapComparator());
for (int i = 0; i < N; ++i) {
heap1.add(v[i]);
if (heap1.size() > K) {
heap1.remove();
}
}
return heap1.peek();
}
public static void main(String[] args)
{
int[] vec
= { 10, 5, 4, 3, 48, 15, 6, 2, 33, 53, 10
};
int N = vec.length;
int K = 4;
System.out.println("Kth Smallest Element: "
+ kthSmallest(vec, N, K));
}
}
Python3import heapq
def kthSmallest(arr, N, K):
pq = []
for i in range(K):
heapq.heappush(pq, arr[i])
heapq._heapify_max(pq)
for i in range(K, N):
if
arr[i] < pq[0]:
heapq.heappop(pq)
heapq.heappush(pq, arr[i])
heapq._heapify_max(pq)
return pq[0]
if __name__ == "__main__":
N = 10
arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
K = 4
print("Kth Smallest Element is:", kthSmallest(arr, N, K))
C#using System;
using System.Collections.Generic;
class GFG {
static int kthSmallest(int[] arr, int N, int K)
{
List<int> pq = new List<int>();
for (int i = 0; i < K; i++) {
pq.Add(arr[i]);
}
for (int i = K; i < N; i++) {
if (arr[i] < pq[0]) {
pq.Sort();
pq.Reverse();
pq.RemoveAt(0);
pq.Add(arr[i]);
}
}
return pq[0];
}
public static void Main()
{
int[] vec
= { 10, 5, 4, 3, 48, 15, 6, 2, 33, 53, 10 };
int N = vec.Length;
int K = 4;
Console.WriteLine("Kth Smallest Element: "
+ kthSmallest(vec, N, K));
}
}
Time
complexity: O(K log K + (N – K) log K)
Auxiliary Space: O(K) K’th smallest element in an unsorted array using Binary Search:The idea to solve this problem is that the Kth smallest element would be the element at the kth position if the array was sorted in increasing order. Using this logic, binary search can be used to predict the index of an element as if the array was sorted but without actually sorting the
array.
Follow the given steps to solve the problem: - Find low and high that is the range where our answer can lie.
- Apply Binary Search on this range.
- If the selected element which would be mid has less than K elements lesser to it then increase the number that islow = mid + 1.
- Otherwise, Decrement the high pointer, i.e high = mid
- The Binary Search will end when only one element
remains in the answer space which would be the answer.
Below is the implementation of the above approach: C++#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int count(vector<int>& nums, int& mid)
{
int cnt = 0;
for (int i = 0; i < nums.size(); i++)
if (nums[i] <= mid)
cnt++;
return cnt;
}
int
kthSmallest(vector<int> nums, int& k)
{
int low = INT_MAX;
int high = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
low = min(low, nums[i]);
high = max(high, nums[i]);
}
while (low < high) {
int mid = low + (high - low) / 2;
if (count(nums, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
int main()
{
vector<int> nums{ 1, 4, 5, 3, 19, 3 };
int k = 3;
cout << "K'th smallest element is "
<< kthSmallest(nums, k);
return 0;
}
Javaimport java.util.Arrays;
import java.util.Collections;
class GFG {
static int count(int[] nums, int mid)
{
int cnt = 0;
for
(int i = 0; i < nums.length; i++)
if (nums[i] <= mid)
cnt++;
return cnt;
}
static int kthSmallest(int[] nums, int k)
{
int low = Integer.MAX_VALUE;
int high = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
low = Math.min(low, nums[i]);
high = Math.max(high, nums[i]);
}
while (low < high) {
int
mid = low + (high - low) / 2;
if (count(nums, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
public static void main(String[] args)
{
int arr[] = { 1, 4, 5, 3, 19, 3 };
int k = 3;
System.out.print("Kth smallest element is "
+ kthSmallest(arr, k));
}
}
Python3import sys
def count(nums, mid):
cnt = 0
for i in range(len(nums)):
if nums[i] <= mid:
cnt += 1
return cnt
def kthSmallest(nums, k):
low = sys.maxsize
high =
-sys.maxsize - 1
for i in range(len(nums)):
low = min(low, nums[i])
high = max(high, nums[i])
while low < high:
mid = low + (high - low) // 2
if count(nums, mid) < k:
low = mid + 1
else:
high =
mid
return low
if __name__ == "__main__":
nums = [1, 4, 5, 3, 19, 3]
k = 3
print("K'th smallest element is", kthSmallest(nums, k))
C#using System;
using System.Collections.Generic;
class GFG {
static int count(int[] nums, int
mid)
{
int cnt = 0;
for (int i = 0; i < nums.Length; i++)
if (nums[i] <= mid)
cnt++;
return cnt;
}
static int kthSmallest(int[] nums, int k)
{
int low = Int32.MaxValue;
int high = Int32.MinValue;
for (int i = 0; i < nums.Length; i++) {
low = Math.Min(low, nums[i]);
high = Math.Max(high, nums[i]);
}
while (low < high) {
int mid = low + (high - low) / 2;
if (count(nums, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
public static void Main()
{
int[] vec = { 1, 4, 5, 3, 19, 3 };
int K = 3;
Console.WriteLine("Kth Smallest Element: "
+ kthSmallest(vec, K));
}
}
Javascript
function count(nums, mid)
{
var cnt = 0;
for(var i = 0; i < nums.length; i++)
if(nums[i] <= mid)
cnt++;
return cnt;
}
function kthSmallest(nums,k){
var low = Number. MAX_VALUE;
var high = Number. MIN_VALUE;
for(var i = 0; i < nums.length; i++)
{
low = Math.min(low, nums[i]);
high = Math.max(high, nums[i]);
}
while(low < high)
{
var mid = Math.floor(low + ((high - low) / 2));
if(count(nums, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
var k = 3;
var nums = [1, 4, 5, 3, 19, 3];
document.write("K'th smallest element is " + kthSmallest(nums, k));
Time complexity: O((mx-mn) * log (mx-mn)), where mn be minimum and mx be
maximum.
Auxiliary Space: O(1) Next: - K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
- K’th Smallest/Largest Element in Unsorted Array |
Set 3 (Worst-Case Linear Time)
How do you find the K largest element in an array?
The previous approach of sorting and finding the Kth largest element is costly.. Initialise a max-heap.. Insert all the elements of the given array into the max heap.. Extract the first K – 1 elements from the heap.. Print the top element of the max heap.. What is KTH in Python?
Kth Largest Element in an Array. Given an integer array nums and an integer k , return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5.
How do you find the kth smallest element in an array in Python?
Solution Steps. Partition the array A[left .. right] into two subarrays A[left .. ... . Computes the number of elements in the subarray A[left .. pos] i.e. count = pos - left + 1.. if (count == K), then A[pos] is the Kth smallest element.. Otherwise determines in which of the two subarrays A[left .. pos-1] and A[pos + 1 ... How do you find the nth highest number in an array?
length; let flag = false; let result = false; while(x < tnum){ y = x + 1; if(y < tnum){ for(z = y; z < tnum; z++){ if(arra[x] < arra[z]){ temp = arra[z]; arra[z] = arra[x]; arra[x] = temp; flag = true; }else{ continue; } } } if(flag){ flag = false; }else{ x++; if(x === highest){ result = true; } } if(result){ break; } ...
| 
