Kth Smallest Element
Description
Given an integer array arr[] and a positive integer k, find and return the kth smallest element in the array.
The kth smallest element is the element that would appear at position k (1-indexed) if the array were sorted in ascending order. For example, in the array [5, 2, 8, 1], the 1st smallest is 1, the 2nd smallest is 2, the 3rd smallest is 5, and the 4th smallest is 8.
It is guaranteed that k is always valid — that is, k is between 1 and the size of the array (inclusive).
Examples
Example 1
Input: arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k = 4
Output: 5
Explanation: If we sort the array, we get [2, 3, 4, 5, 6, 10, 10, 33, 48, 53]. The element at the 4th position (1-indexed) is 5. Note that the duplicate value 10 occupies two separate positions in the sorted order.
Example 2
Input: arr = [7, 10, 4, 3, 20, 15], k = 3
Output: 7
Explanation: Sorting gives [3, 4, 7, 10, 15, 20]. The 3rd smallest element is 7. Notice that the first two smallest values (3 and 4) are smaller than 7, confirming 7 is at position 3.
Example 3
Input: arr = [3, 1], k = 2
Output: 3
Explanation: With only two elements, the sorted array is [1, 3]. The 2nd smallest (and largest) element is 3.
Constraints
- 1 ≤ arr.size() ≤ 10^5
- 1 ≤ arr[i] ≤ 10^5
- 1 ≤ k ≤ arr.size()
Editorial
Brute Force
Intuition
The most natural way to find the kth smallest element is to first put every element in its correct sorted position, then simply pick the one at position k.
Imagine you have a pile of numbered cards thrown on a table. The simplest way to find the 3rd smallest card is to line up all the cards from smallest to largest, then count to the 3rd one. This is exactly what sorting does — it establishes the complete ordering so we can directly read off any positional query.
We sort the entire array in ascending order, then return the element at index k - 1 (since arrays are 0-indexed but k is 1-indexed).
Step-by-Step Explanation
Let's trace through with arr = [7, 10, 4, 3, 20, 15], k = 3:
Step 1: Start with the unsorted array [7, 10, 4, 3, 20, 15]. We need to find the element that would sit at index k - 1 = 2 after sorting.
Step 2: Begin sorting. The smallest element is 3 (originally at index 3). Place it at the front. Array progress: [3, 10, 4, 7, 20, 15].
Step 3: Next smallest is 4 (originally at index 2). Place at index 1. Array: [3, 4, 10, 7, 20, 15].
Step 4: Next smallest is 7. Place at index 2. Array: [3, 4, 7, 10, 20, 15]. We have now positioned the first 3 elements — our answer is at index 2.
Step 5: Complete the sort for the remaining elements: [3, 4, 7, 10, 15, 20]. The algorithm sorts everything regardless of k.
Step 6: Access the sorted array at index k - 1 = 2. The element is 7. Return 7.
Brute Force — Sort Everything, Then Index — Watch how sorting arranges all elements in order, then we simply pick the element at position k. Notice that the algorithm does full work even though we only need one position.
Algorithm
- Sort the input array in ascending order using any standard sorting algorithm.
- Return the element at index k - 1 (converting from 1-indexed k to 0-indexed array access).
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int kthSmallest(vector<int>& arr, int k) {
sort(arr.begin(), arr.end());
return arr[k - 1];
}
};class Solution:
def kthSmallest(self, arr, k):
arr.sort()
return arr[k - 1]import java.util.Arrays;
class Solution {
public int kthSmallest(int[] arr, int k) {
Arrays.sort(arr);
return arr[k - 1];
}
}Complexity Analysis
Time Complexity: O(n log n)
The sorting step dominates. Standard comparison-based sorts (merge sort, quicksort, timsort) run in O(n log n) for an array of n elements. The final index access is O(1). Regardless of the value of k, the algorithm always sorts the entire array.
Space Complexity: O(1) to O(n)
This depends on the sorting algorithm used. In-place sorts like heapsort or introsort use O(1) extra space (beyond the input). Merge sort requires O(n) extra space. Most standard library implementations use a hybrid approach with O(log n) stack space.
Why This Approach Is Not Efficient
The sorting approach always performs O(n log n) work, regardless of k. If k = 1 (finding the minimum), we could answer in O(n) with a single pass — yet sorting still does full O(n log n) work. The problem is that sorting establishes the complete ordering of ALL elements, when we only need to know the ordering at ONE specific position.
Additionally, sorting modifies the original array (or requires an O(n) copy to preserve it).
Key insight: We do not need to fully sort the array. We only need to identify which element belongs at position k. A max-heap of size k can track the k smallest elements while scanning the array in a single pass. When k is small relative to n, this is significantly faster than sorting everything.
Better Approach - Max-Heap
Intuition
Instead of sorting the entire array, we can maintain a "top-k smallest" collection as we scan through the elements. The key data structure for this is a max-heap of size k.
Imagine you are a talent scout looking for the 3 shortest people in a crowd of 100. You do not need to line up all 100 people by height. Instead, you keep a group of 3 candidates. As you spot each new person, you compare their height to the tallest person in your group. If the new person is shorter, they replace the tallest candidate. After scanning everyone, your group of 3 contains the 3 shortest people, and the tallest in this group is the 3rd shortest overall.
A max-heap makes this efficient: the tallest candidate (the heap's maximum) is always accessible in O(1), and inserting or removing elements takes O(log k). Since k ≤ n, and we process each of the n elements once, the total work is O(n log k) — which is better than O(n log n) whenever k is significantly smaller than n.
Step-by-Step Explanation
Let's trace through with arr = [7, 10, 4, 3, 20, 15], k = 3:
Step 1: Initialize an empty max-heap. Our invariant: the heap holds at most k = 3 elements, representing the k smallest values seen so far. The heap's maximum (root) is the largest among these k smallest — which IS the kth smallest.
Step 2: Insert 7. Heap: [7]. Size 1 ≤ 3, no removal needed.
Step 3: Insert 10. Heap: [10, 7] (10 sifts to root). Size 2 ≤ 3, keep both.
Step 4: Insert 4. Heap: [10, 7, 4]. Size 3 = k. The heap is full. The current root (10) is the provisional 3rd smallest.
Step 5: Insert 3. Heap temporarily becomes [10, 7, 4, 3] with size 4. Overflow! Remove the maximum (10). After reheapify: [7, 3, 4]. The value 10 is too large to be among the 3 smallest. New provisional 3rd smallest: 7.
Step 6: Insert 20. Heap becomes [20, 7, 4, 3], size 4. Overflow. Remove max (20). Heap returns to [7, 3, 4]. The value 20 is far too large.
Step 7: Insert 15. Heap becomes [15, 7, 4, 3], size 4. Overflow. Remove max (15). Heap: [7, 3, 4].
Step 8: All elements processed. The heap holds {3, 4, 7} — the 3 smallest values. The root (maximum of these) is 7. Return 7.
Max-Heap of Size k — Tracking the k Smallest Elements — Watch how the max-heap maintains exactly k elements. When overflow occurs, the largest element is evicted — ensuring only the k smallest survive.
Algorithm
- Create an empty max-heap.
- For each element in the array:
a. Insert the element into the max-heap.
b. If the heap size exceeds k, extract the maximum element (remove the root). - After processing all elements, the heap contains exactly the k smallest elements.
- Return the heap's root (the maximum among the k smallest), which is the kth smallest element.
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int kthSmallest(vector<int>& arr, int k) {
// Max-heap: keeps the k smallest elements seen so far
priority_queue<int> maxHeap;
for (int num : arr) {
maxHeap.push(num);
// If heap grows beyond k, remove the largest
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
// The top of the heap is the kth smallest
return maxHeap.top();
}
};import heapq
class Solution:
def kthSmallest(self, arr, k):
# Python's heapq is a min-heap, so we negate values
# to simulate a max-heap
max_heap = []
for num in arr:
heapq.heappush(max_heap, -num)
if len(max_heap) > k:
heapq.heappop(max_heap)
# Negate back to get the actual value
return -max_heap[0]import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
public int kthSmallest(int[] arr, int k) {
// Max-heap using reversed comparator
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) {
maxHeap.offer(num);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
return maxHeap.peek();
}
}Complexity Analysis
Time Complexity: O(n log k)
We iterate through all n elements. For each element, we perform at most one insert (O(log k)) and at most one extract (O(log k)) on a heap of size at most k. Total: n elements × O(log k) per element = O(n log k).
When k is small (e.g., k = 1 for finding the minimum), this approaches O(n). When k = n, it becomes O(n log n) — same as sorting.
Space Complexity: O(k)
The heap stores at most k elements at any time. For small k values, this is very memory-efficient.
Why This Approach Is Not Efficient
The max-heap approach runs in O(n log k), which is a genuine improvement over sorting's O(n log n) when k is small. However, it has limitations:
- When k is proportional to n (e.g., finding the median where k = n/2), O(n log k) degrades to O(n log n) — offering no benefit over sorting.
- The heap maintains a partial ordering of k elements throughout the scan. While this is less work than sorting everything, it still does more structural maintenance than strictly necessary.
Key insight: Both sorting and heap approaches impose ordering on elements — sorting orders ALL elements, the heap orders k elements. But to find ONE specific element, do we need ordering at all? The QuickSelect algorithm uses a fundamentally different strategy: instead of ordering elements, it uses partitioning to narrow down where the kth element lives. Each partition step eliminates a fraction of the elements from consideration, achieving O(n) average time by doing the minimum work required.
Optimal Approach - QuickSelect
Intuition
QuickSelect borrows the partitioning idea from QuickSort but applies it more cleverly. In QuickSort, after partitioning, you recursively sort BOTH halves. In QuickSelect, you only recurse into the half that contains the kth element — the other half is completely ignored.
Here is the core idea: pick a pivot element and partition the array so that all elements ≤ pivot are on the left, and all elements > pivot are on the right. After partitioning, the pivot lands at its correct sorted position. Now:
- If the pivot's position equals k - 1, we found the kth smallest — return it.
- If the pivot's position is greater than k - 1, the kth smallest must be in the left portion — recurse there.
- If the pivot's position is less than k - 1, the kth smallest must be in the right portion — recurse there.
Think of it like a guessing game where each guess eliminates half the remaining candidates. Instead of sorting all 100 playing cards, you pick one card and ask "is the card I want smaller or larger than this one?" Each answer halves the search space. On average, you find the card in O(n) total comparisons — far better than the O(n log n) of full sorting.
The average time complexity is O(n) because each partition roughly halves the problem size: n + n/2 + n/4 + ... ≈ 2n = O(n). The worst case is O(n²) when the pivot is always the smallest or largest element, but this is rare with good pivot selection.
Step-by-Step Explanation
Let's trace through with arr = [7, 10, 4, 3, 20, 15], k = 3 (target index = 2):
Step 1: First partition. Choose pivot = arr[5] = 15. Scan elements against the pivot.
Step 2: Scan: 7 ≤ 15 (left), 10 ≤ 15 (left), 4 ≤ 15 (left), 3 ≤ 15 (left). All four elements are ≤ 15 and stay on the left side.
Step 3: Element 20 > 15. It belongs on the right side of the pivot.
Step 4: Place pivot 15 at position 4: swap arr[4] and arr[5]. Array: [7, 10, 4, 3, 15, 20]. Pivot index = 4.
Step 5: Decision: pivotIndex (4) > target (2). The kth smallest is in the left portion [0..3]. Recurse on [7, 10, 4, 3].
Step 6: Second partition on [7, 10, 4, 3]. Choose pivot = arr[3] = 3. Scan: 7 > 3, 10 > 3, 4 > 3. No elements are ≤ 3.
Step 7: Place pivot 3 at position 0: swap arr[0] and arr[3]. Array: [3, 10, 4, 7, 15, 20]. Pivot index = 0.
Step 8: Decision: pivotIndex (0) < target (2). The kth smallest is in the right portion [1..3]. Recurse on [10, 4, 7].
Step 9: Third partition on [10, 4, 7]. Choose pivot = arr[3] = 7. Scan: 10 > 7 (skip), 4 ≤ 7 (swap to left). After swap: [3, 4, 10, 7, ...].
Step 10: Place pivot 7 at position 2: swap arr[2] and arr[3]. Array: [3, 4, 7, 10, 15, 20]. Pivot index = 2.
Result: pivotIndex (2) == target (2). The element at index 2 is 7. Return 7!
QuickSelect — Partition and Narrow Down — Watch how each partition places the pivot at its correct sorted position, then we recurse ONLY into the side containing our target index — ignoring the other half entirely.
Algorithm
-
Define a partition function:
a. Choose a pivot (e.g., the last element).
b. Rearrange elements so all values ≤ pivot are to its left and all values > pivot are to its right.
c. Return the pivot's final index. -
Define quickSelect(left, right, target):
a. Partition the subarray arr[left..right].
b. If pivotIndex == target, return arr[pivotIndex] (found the kth smallest).
c. If pivotIndex > target, recurse on arr[left..pivotIndex-1] (search left).
d. If pivotIndex < target, recurse on arr[pivotIndex+1..right] (search right). -
Call quickSelect(0, n-1, k-1) to find the kth smallest element.
Code
#include <vector>
using namespace std;
class Solution {
public:
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[right]);
return i;
}
int quickSelect(vector<int>& arr, int left, int right, int target) {
int pivotIndex = partition(arr, left, right);
if (pivotIndex == target) {
return arr[pivotIndex];
} else if (pivotIndex > target) {
return quickSelect(arr, left, pivotIndex - 1, target);
} else {
return quickSelect(arr, pivotIndex + 1, right, target);
}
}
int kthSmallest(vector<int>& arr, int k) {
return quickSelect(arr, 0, arr.size() - 1, k - 1);
}
};class Solution:
def kthSmallest(self, arr, k):
def partition(left, right):
pivot = arr[right]
i = left
for j in range(left, right):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[right] = arr[right], arr[i]
return i
def quick_select(left, right, target):
pivot_index = partition(left, right)
if pivot_index == target:
return arr[pivot_index]
elif pivot_index > target:
return quick_select(left, pivot_index - 1, target)
else:
return quick_select(pivot_index + 1, right, target)
return quick_select(0, len(arr) - 1, k - 1)class Solution {
private int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[right];
arr[right] = temp;
return i;
}
private int quickSelect(int[] arr, int left, int right, int target) {
int pivotIndex = partition(arr, left, right);
if (pivotIndex == target) {
return arr[pivotIndex];
} else if (pivotIndex > target) {
return quickSelect(arr, left, pivotIndex - 1, target);
} else {
return quickSelect(arr, pivotIndex + 1, right, target);
}
}
public int kthSmallest(int[] arr, int k) {
return quickSelect(arr, 0, arr.length - 1, k - 1);
}
}Complexity Analysis
Time Complexity: O(n) average, O(n²) worst case
On average, each partition divides the problem roughly in half. The total work across all partition calls forms a geometric series: n + n/2 + n/4 + n/8 + ... ≈ 2n = O(n). This is because we only recurse into ONE side after each partition — unlike QuickSort which recurses into both.
The worst case occurs when the pivot is always the smallest or largest element (e.g., already sorted array with last-element pivot). Each partition then eliminates only 1 element, leading to n + (n-1) + (n-2) + ... = O(n²). This can be mitigated with randomized pivot selection.
Space Complexity: O(log n) average, O(n) worst case
The recursion depth determines space usage. On average, the recursion depth is O(log n) since each call halves the problem. In the worst case, the recursion depth is O(n). An iterative version can reduce this to O(1).