Get started

Kth Smallest Element — Medium Problem & Solution

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…

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 <= 100000
  • 1 <= k <= arr.length
  • 1 <= arr[i] <= 1000000000
  • All values in arr are distinct.

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

  1. Sort a copy of arr ascending.
  2. Return the element at index k - 1.
  3. For quickselect instead: partition around a pivot at final index p. If p == k - 1 the pivot is the answer; if p > k - 1 recurse 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: k is 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue