.png)
Kth Smallest Element in an Array
Problem Statement
You are given an integer array arr and an integer k.
Your task is to find the k-th smallest element in the array.
1 ≤ k ≤ n
Example 1
Input
arr = [7,10,4,3,20,15]
k = 3
Output
7
Example 2
Input
arr = [3,2,1,5,6,4]
k = 2
Output
2
Why This Problem Is Important
- Extremely frequent interview question
- Tests sorting, heap, partition logic
- Introduces QuickSelect (selection algorithm)
- Asked in FAANG, Amazon, Microsoft, Adobe
- Foundation for Top K / Order Statistics
Approach 1: Sorting
Idea
Sort the array and return the element at index k-1.
Algorithm
- Sort the array
- Return arr[k-1]
Time & Space Complexity
- Time: O(n log n)
- Space: O(1) (in-place sort)
Implementations
C++
#include
using namespace std;
int main() {
int arr[] = {7,10,4,3,20,15};
int k = 3, n = 6;
sort(arr, arr+n);
cout << arr[k-1];
return 0;
}
Java
import java.util.*;
public class KthSmallest {
public static void main(String[] args) {
int[] arr = {7,10,4,3,20,15};
int k = 3;
Arrays.sort(arr);
System.out.println(arr[k-1]);
}
}
Python
arr = [7,10,4,3,20,15]
k = 3
arr.sort()
print(arr[k-1])
JavaScript
let arr = [7,10,4,3,20,15];
let k = 3;
arr.sort((a,b)=>a-b);
console.log(arr[k-1]);
C#
using System;
class Program {
static void Main() {
int[] arr = {7,10,4,3,20,15};
int k = 3;
Array.Sort(arr);
Console.WriteLine(arr[k-1]);
}
}
Output
7
Approach 2: Min Heap
Idea
Insert all elements into a min heap, remove k-1 elements, and the top is the answer.
Algorithm
- Build min heap from array
- Pop k-1 elements
- Return top element
Time & Space Complexity
- Time: O(n + k log n)
- Space: O(n)
Implementations
C++
#include
using namespace std;
int main() {
vector arr = {7,10,4,3,20,15};
int k = 3;
priority_queue, greater> pq(arr.begin(), arr.end());
for(int i = 1; i < k; i++)
pq.pop();
cout << pq.top();
return 0;
}
Java
import java.util.*;
public class KthSmallest {
public static void main(String[] args) {
int[] arr = {7,10,4,3,20,15};
int k = 3;
PriorityQueue pq = new PriorityQueue<>();
for(int x : arr) pq.add(x);
for(int i = 1; i < k; i++)
pq.poll();
System.out.println(pq.peek());
}
}
Python
import heapq
arr = [7,10,4,3,20,15]
k = 3
heapq.heapify(arr)
for _ in range(k-1):
heapq.heappop(arr)
print(arr[0])
JavaScript
// Using simple sort to simulate min-heap behavior
let arr = [7,10,4,3,20,15];
let k = 3;
arr.sort((a,b)=>a-b);
console.log(arr[k-1]);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {7,10,4,3,20,15};
int k = 3;
PriorityQueue pq = new PriorityQueue();
foreach(int x in arr)
pq.Enqueue(x, x);
for(int i = 1; i < k; i++)
pq.Dequeue();
Console.WriteLine(pq.Peek());
}
}
Output
7
Approach 3: Max Heap (Size k)
Idea
Maintain a max heap of size k.
If heap size exceeds k, remove the largest element.
Algorithm
- Traverse array
- Push element into max heap
- If heap size > k, pop
- Heap top is answer
Time & Space Complexity
- Time: O(n log k)
- Space: O(k)
C++
#include
using namespace std;
int main() {
int arr[] = {7,10,4,3,20,15};
int n = 6, k = 3;
priority_queue pq;
for(int i = 0; i < n; i++) {
pq.push(arr[i]);
if(pq.size() > k)
pq.pop();
}
cout << pq.top();
return 0;
}
Java
import java.util.*;
public class KthSmallest {
public static void main(String[] args) {
int[] arr = {7,10,4,3,20,15};
int k = 3;
PriorityQueue pq =
new PriorityQueue<>(Collections.reverseOrder());
for(int x : arr) {
pq.add(x);
if(pq.size() > k)
pq.poll();
}
System.out.println(pq.peek());
}
}
Python
import heapq
arr = [7,10,4,3,20,15]
k = 3
heap = []
for x in arr:
heapq.heappush(heap, -x)
if len(heap) > k:
heapq.heappop(heap)
print(-heap[0])
JavaScript
// Simulating max heap using sorting (since JS lacks built-in heap)
let arr = [7,10,4,3,20,15];
let k = 3;
let heap = [];
for (let x of arr) {
heap.push(x);
heap.sort((a,b)=>b-a); // max heap behavior
if (heap.length > k)
heap.pop();
}
console.log(heap[0]);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {7,10,4,3,20,15};
int k = 3;
PriorityQueue pq =
new PriorityQueue();
foreach(int x in arr) {
pq.Enqueue(x, -x); // max heap using negative priority
if(pq.Count > k)
pq.Dequeue();
}
Console.WriteLine(pq.Peek());
}
}
Output
7
Approach 4: QuickSelect (Optimal)
Idea
Based on QuickSort partitioning, but only processes one side.
Algorithm
- Choose pivot
- Partition array
- If pivot index == k-1 → answer
- Else recurse left or right
Time & Space Complexity
- Time: O(n) average
- Space: O(1)
C++
#include
using namespace std;
int partition(int arr[], int l, int r) {
int pivot = arr[r];
int i = l;
for(int j = l; j < r; j++) {
if(arr[j] <= pivot) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[r]);
return i;
}
int quickSelect(int arr[], int l, int r, int k) {
if(l <= r) {
int p = partition(arr, l, r);
if(p == k) return arr[p];
else if(p > k) return quickSelect(arr, l, p-1, k);
else return quickSelect(arr, p+1, r, k);
}
return -1;
}
int main() {
int arr[] = {7,10,4,3,20,15};
int n = 6, k = 3;
cout << quickSelect(arr, 0, n-1, k-1);
return 0;
}
Java
import java.util.*;
public class KthSmallestQuickSelect {
static int partition(int[] arr, int l, int r) {
int pivot = arr[r];
int i = l;
for(int j = l; j < r; j++) {
if(arr[j] <= pivot) {
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;
}
static int quickSelect(int[] arr, int l, int r, int k) {
if(l <= r) {
int p = partition(arr, l, r);
if(p == k) return arr[p];
else if(p > k) return quickSelect(arr, l, p-1, k);
else return quickSelect(arr, p+1, r, k);
}
return -1;
}
public static void main(String[] args) {
int[] arr = {7,10,4,3,20,15};
int k = 3;
System.out.println(quickSelect(arr, 0, arr.length-1, k-1));
}
}
Python
def quickselect(arr, k):
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k <= len(left):
return quickselect(left, k)
elif k <= len(left) + len(mid):
return pivot
else:
return quickselect(right, k - len(left) - len(mid))
arr = [7,10,4,3,20,15]
k = 3
print(quickselect(arr, k))
JavaScript
function quickSelect(arr, k) {
if (arr.length === 1) return arr[0];
let pivot = arr[Math.floor(arr.length / 2)];
let left = arr.filter(x => x < pivot);
let mid = arr.filter(x => x === pivot);
let right = arr.filter(x => x > pivot);
if (k <= left.length)
return quickSelect(left, k);
else if (k <= left.length + mid.length)
return pivot;
else
return quickSelect(right, k - left.length - mid.length);
}
let arr = [7,10,4,3,20,15];
let k = 3;
console.log(quickSelect(arr, k));
C#
using System;
using System.Linq;
class Program {
static int QuickSelect(int[] arr, int k) {
int pivot = arr[arr.Length / 2];
var left = arr.Where(x => x < pivot).ToArray();
var mid = arr.Where(x => x == pivot).ToArray();
var right = arr.Where(x => x > pivot).ToArray();
if (k <= left.Length)
return QuickSelect(left, k);
else if (k <= left.Length + mid.Length)
return pivot;
else
return QuickSelect(right, k - left.Length - mid.Length);
}
static void Main() {
int[] arr = {7,10,4,3,20,15};
int k = 3;
Console.WriteLine(QuickSelect(arr, k));
}
}
Output
7
Summary
- Sorting is simplest but slower
- Heaps are best for streaming / large data
- Max Heap (k size) is very efficient
- QuickSelect is interview favorite
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
