K’th Smallest/Largest Element in Unsorted Array | Expected Linear Time
Last Updated :
24 Mar, 2025
Given an array of distinct integers and an integer k, where k is smaller than the array’s size, the task is to find the k’th smallest element in the array.
Examples:
Input: arr = [7, 10, 4, 3, 20, 15], k = 3
Output: 7
Explanation: The sorted array is [3, 4, 7, 10, 15, 20], so the 3rd smallest element is 7.
Input: arr = [7, 10, 4, 3, 20, 15], k = 4
Output: 10
Explanation: The sorted array is [3, 4, 7, 10, 15, 20], so the 4th smallest element is 10.
Please note that there are multiple ways to solve this problem discussed in kth-Smallest/Largest Element in Unsorted Array. The solution discussed here works best in practice.
The idea is to use a randomized pivot selection to partition the array, reducing the search space by focusing on the subarray where the k’th element must lie.
Step by step approach:
Choose a Random Pivot: Randomly select an element as the pivot. This helps avoid the worst-case scenario in some cases (like when the array is already sorted).
Partitioning: Rearrange the array such that all elements less than the pivot are on the left side, and those greater than the pivot are on the right side.
Recursive Search: Once the pivot is positioned, if its index equals n-k comparison , then it’s the Kth largest element. If not, recursively search the appropriate partition (left or right) based on the with n-k.
C++
// C++ program to find K’th Smallest/
// Largest Element in Unsorted Array
#include<bits/stdc++.h>
using namespace std;
// Partition function: Rearranges elements
// around a pivot (last element)
int partition(vector<int> &arr, int l, int r) {
int x = arr[r];
int i = l;
// Iterate through the subarray
for (int j = l; j <= r - 1; j++) {
// Move elements <= pivot to the
// left partition
if (arr[j] <= x) {
swap(arr[i], arr[j]);
i++;
}
}
// Place the pivot in its correct position
swap(arr[i], arr[r]);
return i;
}
// Randomizes the pivot to avoid worst-case performance
int randomPartition(vector<int> &arr, int l, int r) {
int n = r - l + 1;
int pivot = rand() % n;
swap(arr[l + pivot], arr[r]);
return partition(arr, l, r);
}
// function to find the k'th smallest element
// using QuickSelect
int quickSelect(vector<int> &arr, int l, int r, int k) {
// Check if k is within the valid range
// of the current subarray
if (k > 0 && k <= r - l + 1) {
// Partition the array and get the
// pivot's final position
int pos = randomPartition(arr, l, r);
// If pivot is the k'th element, return it
if (pos - l == k - 1)
return arr[pos];
// If pivot's position is larger than k,
// search left subarray
if (pos - l > k - 1)
return quickSelect(arr, l, pos - 1, k);
// Otherwise, search right subarray and adjust k
// (k is reduced by the size of the left partition)
return quickSelect(arr, pos + 1, r, k - (pos - l + 1));
}
// Return infinity for invalid k (error handling)
return INT_MAX;
}
int kthSmallest(vector<int> &arr, int k) {
int n = arr.size();
return quickSelect(arr, 0, n-1, k);
}
int main() {
vector<int> arr = {12, 3, 5, 7, 4, 19, 26};
int k = 3;
cout << kthSmallest(arr, k);
return 0;
}
// Java program to find K’th Smallest/
// Largest Element in Unsorted Array
import java.util.Random;
class GfG {
// Partition function: Rearranges elements
// around a pivot (last element)
static int partition(int[] arr, int l, int r) {
int x = arr[r];
int i = l;
// Iterate through the subarray
for (int j = l; j <= r - 1; j++) {
// Move elements <= pivot to the left partition
if (arr[j] <= x) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
// Place the pivot in its correct position
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
return i;
}
// Randomizes the pivot to avoid worst-case performance
static int randomPartition(int[] arr, int l, int r) {
Random rand = new Random();
int n = r - l + 1;
int pivot = rand.nextInt(n);
int temp = arr[l + pivot];
arr[l + pivot] = arr[r];
arr[r] = temp;
return partition(arr, l, r);
}
// function to find the k'th smallest element using QuickSelect
static int quickSelect(int[] arr, int l, int r, int k) {
// Check if k is within the valid range of
// the current subarray
if (k > 0 && k <= r - l + 1) {
// Partition the array and get the
// pivot's final position
int pos = randomPartition(arr, l, r);
// If pivot is the k'th element, return it
if (pos - l == k - 1)
return arr[pos];
// If pivot's position is larger than k,
// search left subarray
if (pos - l > k - 1)
return quickSelect(arr, l, pos - 1, k);
// Otherwise, search right subarray and adjust k
// (k is reduced by the size of the left partition)
return quickSelect(arr, pos + 1, r, k - (pos - l + 1));
}
// Return infinity for invalid k (error handling)
return Integer.MAX_VALUE;
}
static int kthSmallest(int[] arr, int k) {
int n = arr.length;
return quickSelect(arr, 0, n - 1, k);
}
public static void main(String[] args) {
int[] arr = {12, 3, 5, 7, 4, 19, 26};
int k = 3;
System.out.println(kthSmallest(arr, k));
}
}
# Python program to find K’th Smallest/
# Largest Element in Unsorted Array
import random
# Partition function: Rearranges elements
# around a pivot (last element)
def partition(arr, l, r):
x = arr[r]
i = l
# Iterate through the subarray
for j in range(l, r):
# Move elements <= pivot to the left partition
if arr[j] <= x:
arr[i], arr[j] = arr[j], arr[i]
i += 1
# Place the pivot in its correct position
arr[i], arr[r] = arr[r], arr[i]
return i
# Randomizes the pivot to avoid worst-case performance
def randomPartition(arr, l, r):
n = r - l + 1
pivot = random.randint(0, n - 1)
arr[l + pivot], arr[r] = arr[r], arr[l + pivot]
return partition(arr, l, r)
# function to find the k'th smallest element using QuickSelect
def quickSelect(arr, l, r, k):
# Check if k is within the valid range of the current subarray
if 0 < k <= r - l + 1:
# Partition the array and get the pivot's final position
pos = randomPartition(arr, l, r)
# If pivot is the k'th element, return it
if pos - l == k - 1:
return arr[pos]
# If pivot's position is larger than k, search left subarray
if pos - l > k - 1:
return quickSelect(arr, l, pos - 1, k)
# Otherwise, search right subarray and adjust k
# (k is reduced by the size of the left partition)
return quickSelect(arr, pos + 1, r, k - (pos - l + 1))
# Return infinity for invalid k (error handling)
return float('inf')
def kthSmallest(arr, k):
n = len(arr)
return quickSelect(arr, 0, n - 1, k)
if __name__ == "__main__":
arr = [12, 3, 5, 7, 4, 19, 26]
k = 3
print(kthSmallest(arr, k))
// C# program to find K’th Smallest/
// Largest Element in Unsorted Array
using System;
class GfG {
// Partition function: Rearranges elements
// around a pivot (last element)
static int partition(int[] arr, int l, int r) {
int x = arr[r];
int i = l;
// Iterate through the subarray
for (int j = l; j <= r - 1; j++) {
// Move elements <= pivot to the left partition
if (arr[j] <= x) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
// Place the pivot in its correct position
int temp2 = arr[i];
arr[i] = arr[r];
arr[r] = temp2;
return i;
}
// Randomizes the pivot to avoid worst-case performance
static int randomPartition(int[] arr, int l, int r) {
Random rand = new Random();
int n = r - l + 1;
int pivot = rand.Next(n);
int temp = arr[l + pivot];
arr[l + pivot] = arr[r];
arr[r] = temp;
return partition(arr, l, r);
}
// function to find the k'th smallest element using QuickSelect
static int quickSelect(int[] arr, int l, int r, int k) {
// Check if k is within the valid range of the
// current subarray
if (k > 0 && k <= r - l + 1) {
// Partition the array and get the pivot's
// final position
int pos = randomPartition(arr, l, r);
// If pivot is the k'th element, return it
if (pos - l == k - 1)
return arr[pos];
// If pivot's position is larger than k, search
// left subarray
if (pos - l > k - 1)
return quickSelect(arr, l, pos - 1, k);
// Otherwise, search right subarray and adjust k
// (k is reduced by the size of the left partition)
return quickSelect(arr, pos + 1, r, k - (pos - l + 1));
}
// Return infinity for invalid k (error handling)
return int.MaxValue;
}
static int kthSmallest(int[] arr, int k) {
int n = arr.Length;
return quickSelect(arr, 0, n - 1, k);
}
static void Main() {
int[] arr = {12, 3, 5, 7, 4, 19, 26};
int k = 3;
Console.WriteLine(kthSmallest(arr, k));
}
}
// JavaScript program to find K’th Smallest/
// Largest Element in Unsorted Array
// Partition function: Rearranges elements
// around a pivot (last element)
function partition(arr, l, r) {
let x = arr[r];
let i = l;
// Iterate through the subarray
for (let j = l; j <= r - 1; j++) {
// Move elements <= pivot to the left partition
if (arr[j] <= x) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
// Place the pivot in its correct position
[arr[i], arr[r]] = [arr[r], arr[i]];
return i;
}
// Randomizes the pivot to avoid worst-case performance
function randomPartition(arr, l, r) {
let n = r - l + 1;
let pivot = Math.floor(Math.random() * n);
[arr[l + pivot], arr[r]] = [arr[r], arr[l + pivot]];
return partition(arr, l, r);
}
// function to find the k'th smallest element using QuickSelect
function quickSelect(arr, l, r, k) {
// Check if k is within the valid range of the current subarray
if (k > 0 && k <= r - l + 1) {
// Partition the array and get the pivot's final position
let pos = randomPartition(arr, l, r);
// If pivot is the k'th element, return it
if (pos - l == k - 1)
return arr[pos];
// If pivot's position is larger than k, search left subarray
if (pos - l > k - 1)
return quickSelect(arr, l, pos - 1, k);
// Otherwise, search right subarray and adjust k
// (k is reduced by the size of the left partition)
return quickSelect(arr, pos + 1, r, k - (pos - l + 1));
}
// Return Infinity for invalid k (error handling)
return Infinity;
}
function kthSmallest(arr, k) {
let n = arr.length;
return quickSelect(arr, 0, n - 1, k);
}
let arr = [12, 3, 5, 7, 4, 19, 26];
let k = 3;
console.log(kthSmallest(arr, k));
Time Complexity: O(n) The worst-case time complexity of the above solution is still O(n2). In the worst case, the randomized function may always pick a corner element. However, the average-case time complexity is O(n). The assumption in the analysis is, random number generator is equally likely to generate any number in the input range.
Auxiliary Space: O(1) since using constant variables.
Even if the worst case time complexity is quadratic, this solution works best in practice.
Similar Reads
K'th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
Given an array and a number k where k is smaller than the size of the array, we need to find the k’th largest element in the given array. It is given that all array elements are distinct. We recommend reading the following post as a prerequisite to this post. K’th Smallest/Largest Element in Unsorte
9 min read
K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time
Given an array of distinct integers arr[] and an integer k. The task is to find the k-th smallest element in the array. For better understanding, k refers to the element that would appear in the k-th position if the array were sorted in ascending order. Note: k will always be less than the size of t
15 min read
K’th Smallest Element in Unsorted Array
Given an array arr[] of N distinct elements and a number K, where K is smaller than the size of the array. Find the K'th smallest element in the given array. 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 Table of Content [Naive
15+ min read
Largest element in the array that is repeated exactly k times
Given an array of integers and an integer 'k', the task is to find the largest element from the array that is repeated exactly 'k' times. Examples: Input: arr = {1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6}, k = 2 Output: 5 The elements that exactly occur 2 times are 1, 3 and 5 And, the largest element among th
15 min read
kth smallest/largest in a small range unsorted array
Find kth smallest or largest element in an unsorted array, where k<=size of array. It is given that elements of array are in small range. Examples: Input : arr[] = {3, 2, 9, 5, 7, 11, 13} k = 5 Output: 9 Input : arr[] = {16, 8, 9, 21, 43} k = 3 Output: 16 Input : arr[] = {50, 50, 40} k = 2 Output
5 min read
Find the Kth smallest element in the sorted generated array
Given an array arr[] of N elements and an integer K, the task is to generate an B[] with the following rules: Copy elements arr[1...N], N times to array B[].Copy elements arr[1...N/2], 2*N times to array B[].Copy elements arr[1...N/4], 3*N times to array B[].Similarly, until only no element is left
8 min read
Python heapq to find K'th smallest element in a 2D array
Given an n x n matrix and integer k. Find the k'th smallest element in the given 2D array. Examples: Input : mat = [[10, 25, 20, 40], [15, 45, 35, 30], [24, 29, 37, 48], [32, 33, 39, 50]] k = 7 Output : 7th smallest element is 30 We will use similar approach like K’th Smallest/Largest Element in Uns
3 min read
k-th missing element in an unsorted array
Given an unsorted sequence a[], the task is to find the K-th missing contiguous element in the increasing sequence of the array elements i.e. consider the array in sorted order and find the kth missing number. If no k-th missing element is there output -1. Note: Only elements exists in the range of
6 min read
Print X array elements closest to the Kth smallest element in the array
Given two integers K, X, and an array arr[] consisting of N distinct elements, the task is to find X elements closest to the Kth smallest element from the given array. Examples: Input: arr[] = {1, 2, 3, 4, 10}, K = 3, X = 2Output: 2 3Explanation: Kth smallest element present in the given array is 3
15+ min read
Print n smallest elements from given array in their original order
We are given an array of m-elements, we need to find n smallest elements from the array but they must be in the same order as they are in given array. Examples: Input : arr[] = {4, 2, 6, 1, 5}, n = 3 Output : 4 2 1 Explanation : 1, 2 and 4 are 3 smallest numbers and 4 2 1 is their order in given arr
5 min read