Kth Smallest Element — Solution in Python, Java & C++
Kth Smallest Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Kth Smallest Element is a medium coding problem on arrays, sorting and quickselect, asked in Amazon, Microsoft and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Quickselect
- Asked at: Amazon, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array arr of distinct integers and a number k, return the k-th smallest element — the value that would sit at index k - 1 if the array were sorted ascending.
k is 1-based and always valid.
Example 1
Input: arr = [7,10,4,3,20,15], k = 3
Output: 7
Explanation: Sorted it is [3,4,7,10,15,20]; the 3rd value is 7.
Example 2
Input: arr = [7,10,4,20,15], k = 4
Output: 15
Example 3
Input: arr = [5], k = 1
Output: 5
Constraints
1 <= arr.length <= 1000001 <= k <= arr.length1 <= arr[i] <= 1000000000All values in arr are distinct.
Hints for Kth Smallest Element
Hint 1
Sorting and indexing is O(n log n) and completely acceptable.
Hint 2
The interview answer is quickselect: partition like quicksort, but recurse into only the side that contains index
k - 1.Hint 3
A max-heap of size
kis the third standard route and streams the input.
How to solve Kth Smallest Element
Sorting puts the answer at index k - 1 by definition. The faster route is quickselect: partition around a pivot and recurse into only the half that can hold the target index, which averages linear time.
Approach
- Sort a copy of
arrascending. - Return the element at index
k - 1. - For quickselect instead: partition around a pivot at final index
p. Ifp == k - 1the pivot is the answer; ifp > k - 1recurse left, otherwise recurse right.
Why it works
After partitioning, the pivot is in its final sorted position, so comparing p with k - 1 tells you which side holds the answer — the other side can be discarded entirely. Halving the work each time gives O(n) expected total.
Complexity
- Time —
O(n log n) sorting, O(n) expected with quickselect - Space —
O(n) for the copy, O(1) extra for in-place quickselect
Pitfalls
- Off-by-one:
kis 1-based but array indices are 0-based. - Quickselect degrades to O(n²) on adversarial pivots — randomise or use median-of-three.
Reference solution
Python
from typing import List
def kthSmallest(arr: List[int], k: int) -> int:
return sorted(arr)[k - 1]Java
public static int kthSmallest(int[] arr, int k) {
int[] s = arr.clone();
Arrays.sort(s);
return s[k - 1];
}C++
int kthSmallest(vector<int>& arr, int k) {
vector<int> s = arr;
nth_element(s.begin(), s.begin() + (k - 1), s.end());
return s[k - 1];
}JavaScript
var kthSmallest = function(arr, k) {
var s = arr.slice().sort(function(a, b) { return a - b; });
return s[k - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms